An improved bound for the strong clique index of graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.02698
curl -X POST /api/v1/records/arxiv/2607.02698/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.02698/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'