Linearly -bounding (P₆, C₄)-free graphs

DOI10.1002/JGT.22456MaRDI QIDQ5207472zbMATH OpenOpenAlexFDO

Authors Serge Gaspers, Shenwei Huang

Publication date 30 December 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.09750

zbMATH Keywords

approximation algorithmforbidden induced subgraphsgraph coloringlinear \(\chi \)-boundstructure theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Abstract: Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no 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 $chi(G)lefrac32omega(G)$, where $chi(G)$ and $omega(G)$ are the chromatic number and clique number of $G$, respectively. %Our bound is attained by $C_5$ 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 $(P_6,C_4)$-free graphs other than $K_4$ (see cite{HH17}). The new result unifies previously known results on the existence of linear $chi$-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 $frac32omega(G)$ colors for any $(P_6,C_4)$-free graph $G$ in $O(n^{2}m)$ time.

Recommendations

• Linearly \(\chi\)-bounding \((P_6,C_4)\)-free graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• Square-Free Graphs with No Six-Vertex Induced Path
• An optimal χ‐bound for (P6, diamond)‐free graphs
• THE CHROMATIC NUMBER OF -FREE GRAPHS

Cited in

(12)

• Linearly \(\chi\)-bounding \((P_6,C_4)\)-free graphs
• A better upper bound on the chromatic number of (cap, even-hole)-free graphs
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
• THE CHROMATIC NUMBER OF -FREE GRAPHS
• An optimal χ‐bound for (P6, diamond)‐free graphs
• Strengthening Brooks' chromatic bound on \(P_6\)-free graphs
• Structure and linear-Pollyanna for some square-free graphs
• Structure and coloring of a family of (P₇, C₅)-free graphs
• -boundedness and related problems on graphs without long induced paths: a survey
• Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
• Nearly optimal coloring of some C₄-free graphs

This page was built for publication: Linearly \(\chi \)-bounding \((P_6, C_4)\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207472)