Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings
Jessica M. McDonald, Gregory J. Puleo · Journal of Graph Theory · 2022
Abstract Let be a graph with , and let be obtained from by gluing in vertex‐disjoint copies of . We prove that if contains at most one odd cycle of length exceeding 3, or if contains at most three triangles, then . This proves the Strong Coloring Conjecture for such graphs . For graphs with that are not covered by our theorem, we prove an approximation result towards the conjecture.