Square-free graphs with no six-vertex induced path

T. Karthick; Frederic Maffray

paper

Square-free graphs with no six-vertex induced path

arXiv:1805.05007

Abstract

We elucidate the structure of $(P_{6}, C_{4})$ -free graphs by showing that every such graph either has a clique cutset, or a universal vertex, or belongs to several special classes of graphs. Using this result, we show that for any $(P_{6}, C_{4})$ -free graph $G$ , $⌈ \frac{5 I ¨ ( G )}{4} ⌉$ and $⌈ \frac{I ^ ( G ) + I ¨ ( G ) + 1}{2} ⌉$ are tight upper bounds for the chromatic number of $G$ . Moreover, our structural results imply that every ( $P_{6}$ , $C_{4}$ )-free graph with no clique cutset has bounded clique-width, and thus the existence of a polynomial-time algorithm that computes the chromatic number (or stability number) of any $(P_{6}, C_{4})$ -free graph.

Extended abstract accepted for presentation in ICGT-2018, Lyon, France