Edge list coloring graphs whose odd cycles have small intersections
Gregory J. Puleo · arXiv (Cornell University) · 2015
We study the class of graphs $\mathcal{G}^*$ for which every pair of distinct odd cycles intersects in at most one edge. This class of graphs contains the previously-studied class $\mathcal{G}(1)$ of graphs with no odd cycle of length greater than $3$. We give a structural characterization of the graphs in $\mathcal{G}^*$, analogous to the structural characterization of $\mathcal{G}(1)$ given by Hsu, Ikura, and Nemhauser and by Maffray. We characterize the kernel-perfect strict orientations of line graphs $L(G)$ for $G \in \mathcal{G}^*$, thereby partially extending a theorem of Maffray characterizing such orientations for $G \in \mathcal{G}(1)$, and prove that $\chi'_{l}(G) \leq \Delta(G)+1$ for $G \in \mathcal{G}^*$, thereby extending a theorem of McDonald proving the same inequality for $G \in \mathcal{G}(1)$.