Premium
Linearly χ ‐bounding ( P 6 , C 4 )‐free graphs*
Author(s) -
Gaspers Serge,
Huang Shenwei
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22456
Subject(s) - combinatorics , mathematics , perfect graph , split graph , discrete mathematics , cograph , induced subgraph , block graph , triangle free graph , chordal graph , clique number , graph , vertex (graph theory) , line graph , pathwidth , 1 planar graph
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.