The strong clique index of a graph with forbidden cycles

Abstract Given a graph G , the strong clique index of G , denoted ω 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 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 G is a C 2 k ‐free graph with Δ ( G ) ≥ max { 4 , 2 k − 2 } , then ω S ( G ) ≤ ( 2 k − 1 ) Δ ( G ) −2 k − 1 2 , and if G is a C 2 k ‐free bipartite graph, then ω S ( G ) ≤ k Δ ( 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 2 k} ‐free graph G with Δ ( G ) ≥ 1 satisfies ω S ( G ) ≤ k Δ ( G ) − ( k − 1 ) , when either k ≥ 4 or k ∈ { 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 ≥ 3 , we prove that a C 2 k ‐free graph G with Δ ( G ) ≥ 1 satisfies ω S ( G ) ≤ ( 2 k − 1 ) Δ ( G ) + ( 2 k − 1 ) 2 . This improves some results of Cames van Batenburg, Kang, and Pirot.