2017/09/27 by Serge Gaspers, Gaspers, Serge, Shenwei Huang +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1709.09750
openalex publication_date 2017/09/27 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no subgraph isomorphic to H1 or H2. Let Pt and Cs be the path on t vertices and the cycle on s vertices, respectively. In this paper we show that for any (P6,C4)-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 C5 and the Petersen graph. Our bound is attained by several graphs, for instance, the five-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all 4-critical (P6,C4)-free graphs other than K4 (see \citeHH17). 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 (P6,C4)-free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time 3/2-approximation algorithm for coloring (P6,C4)-free graphs. Our algorithm computes a coloring with (3)/(2)ω(G) colors for any (P6,C4)-free graph G in O(n2m) time.