The strong clique index of a graph with forbidden cycles - Cho, Eun Kyung; Choi, Ilkyoo; Kim, Ringi; Park, Boram (Journal of Graph Theory, 2021)
Given a graph (Formula presented.), the strong clique index of (Formula presented.), denoted (Formula presented.), is the maximum size of a set (Formula presented.) of edges such that every pair of edges in (Formula presented.) has distance at most 2 in the line graph of (Formula presented.). 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 index, 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 (Formula presented.) is a (Formula presented.) -free graph with (Formula presented.), then (Formula presented.), and if (Formula presented.) is a (Formula presented.) -free bipartite graph, then (Formula presented.). 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 (Formula presented.) -free graph (Formula presented.) with (Formula presented.) satisfies (Formula presented.), when either (Formula presented.) or (Formula presented.) and (Formula presented.) is also (Formula presented.) -free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for (Formula presented.), we prove that a (Formula presented.) -free graph (Formula presented.) with (Formula presented.) satisfies (Formula presented.). This improves some results of Cames van Batenburg, Kang, and Pirot.
Keywords: Bipartite graphs; Even cycles; Free graphs; Line graph; Maximum degree; Odd cycle; Strong chromatic index; Upper Bound; cycle; strong clique index