The strong clique number of graphs with forbidden cycles

Abstract

Given a graph $G$, the strong clique number of $G$, denoted ${\omega }_S(G)$, is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the line graph of $G$. As a relaxation of the renowned Erdős--Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$-free graph, then ${\omega }_S(G)\le (2k-1)\Delta (G)-\left(\genfrac{}{}{0ex}{}{2k-1}{2}\right)$, and if $G$ is a $C_{2k}$-free bipartite graph, then ${\omega }_S(G)\le k\Delta (G)-(k-1)$. We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a $\{C_5,C_{2k}\}$-free graph $G$ with $\Delta (G)\ge 1$ satisfies ${\omega }_S(G)\le k\Delta (G)-(k-1)$, when either $k\ge 4$ or $k\in \{2,3\}$ and $G$ is also $C_3$-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $k\ge 3$, we prove that a $C_{2k}$-free graph $G$ with $\Delta (G)\ge 1$ satisfies ${\omega }_S(G)\le (2k-1)\Delta (G)+(2k-1{)}^2$. This improves some results of Cames van Batenburg, Kang, and Pirot.

15 pages, 7 figures