On the structure of (pan, even hole)‐free graphs
Kathie Cameron, Steven Chaplick, Chı́nh T. Hoàng · Journal of Graph Theory · 2017
Abstract A hole is a chordless cycle with at least four vertices. A pan is a graph that consists of a hole and a single vertex with precisely one neighbor on the hole. An even hole is a hole with an even number of vertices. We prove that a (pan, even hole)‐free graph can be decomposed by clique cutsets into essentially unit circular‐arc graphs. This structure theorem is the basis of our ‐time certifying algorithm for recognizing (pan, even hole)‐free graphs and for our ‐time algorithm to optimally color them. Using this structure theorem, we show that the tree‐width of a (pan, even hole)‐free graph is at most 1.5 times the clique number minus 1, and thus the chromatic number is at most 1.5 time the clique number.