Linearly χ ‐bounding ( P 6 , C 4 )‐free graphs*

Given two graphs H 1 and H 2 , a graph G is ( H 1 , H 2 ) ‐free if it contains no induced subgraph isomorphic to H 1 or H 2 . Let P t and C s be the path on t vertices and the cycle on s vertices, respectively. In this paper we show that for any ( P 6 , C 4 ) ‐free graph G it holds that χ ( G ) ≤ ( 3 / 2 ) ω ( G ) , where χ ( G ) and ω ( G ) are the chromatic number and clique number of G , respectively. Our bound is attained by several graphs, for instance, the 5‐cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all 4 ‐critical ( P 6 , C 4 ) ‐free graphs other than K 4 (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear χ ‐binding functions for several graph classes. Our proof is based on a novel structure theorem on ( P 6 , C 4 ) ‐free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time 3 ∕ 2 ‐approximation algorithm for coloring ( P 6 , C 4 ) ‐free graphs. Our algorithm computes a coloring with ( 3 / 2 ) ω ( G )colors for any ( P 6 , C 4 ) ‐free graph G in O ( n 2 m ) time.