$\chi$-bounds, operations and chords

Abstract

A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is \emph{long-unichord-free} if it does not contain any long-unichord. We prove a structure theorem for long-unichord-free graph. We give an $O(n^{4}m)$-time algorithm to recognize them. We show that any long-unichord-free graph $G$ can be colored with at most $O({\omega }^3)$ colors, where $\omega$ is the maximum number of pairwise adjacent vertices in $G$.

References in corpus (1)

• A structure theorem for graphs with no cycle with a unique chord and its consequences

Cited by in corpus (2)

• Treewidth versus clique number. I. Graph classes with a forbidden structure
• Coloring of ($P_5$, $4$-wheel)-free graphs