{"id":"arxiv/2607.02698","url":"https://arxiv.org/abs/2607.02698","tags":["math.CO"],"score":0,"title":"An improved bound for the strong clique index of graphs","domain":"math.CO","source":"arxiv","authors":["Hitesh Kumar","Bojan Mohar","Shivaramakrishna Pragada"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$ with line graph $L(G)$, $χ(L(G)^2)$ and $ω(L(G)^2)$ are called the \\emph{strong chromatic index} and \\emph{strong clique index} of $G$, respectively. A well-known conjecture of Erdős and Nešetřil (1985) posits that $χ(L(G)^2)\\le \\frac{5}{4}Δ(G)^2$. Related to that, Faudree, Gyárfás, Schelp and Tuza (1990) conjectured that $ω(L(G)^2) \\le \\frac{5}{4}Δ(G)^2$. We show that $ω(L(G)^2) \\le \\frac{2607}{1987}Δ(G)^2 < \\frac{21}{16}Δ(G)^2$ improving the upper bound $\\frac{4}{3}Δ(G)^2$ of Faron and Postle. Indeed, we make progress towards a stronger conjecture of Faron and Postle in…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}