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.
This paper was written during the 6th Korean Early Career Researcher Workshop in Combinatorics. Eun\u2010Kyung Cho was supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education (No. NRF\u20102020R1I1A1A0105858711). Ilkyoo Choi was supported by the Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education (No. NRF\u20102018R1D1A1B07043049), and also by the Hankuk University of Foreign Studies Research Fund. Ringi Kim was supported by the National Research Foundation of Korea grant funded by the Korea government (No. NRF\u20102021R1C1C1010763), and also by INHA UNIVERSITY Research Fund. Boram Park was supported by the National Research Foundation of Korea grant funded by the Korea government (No. NRF\u20102018R1C1B6003577).
