(2P₂,K₄)-free graphs are 4-colorable

DOI10.1137/18M1205832MaRDI QIDQ5232143zbMATH OpenFDO

Authors Serge Gaspers, Shenwei Huang

Publication date 29 August 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmgraph coloringforbidden induced subgraphs\(\chi\)-bound

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Abstract: In this paper, we show that every $(2P_2,K_4)$-free graph is 4-colorable. The bound is attained by the five-wheel and the complement of the seven-cycle. This answers an open question by Wagon cite{Wa80} in the 1980s. Our result can also be viewed as a result in the study of the Vizing bound for graph classes. A major open problem in the study of computational complexity of graph coloring is whether coloring can be solved in polynomial time for $(4P_1,C_4)$-free graphs. Lozin and Malyshev cite{LM17} conjecture that the answer is yes. As an application of our main result, we provide the first positive evidence to the conjecture by giving a 2-approximation algorithm for coloring $(4P_1,C_4)$-free graphs.

Recommendations

• Triangle-free \(2P_3\)-free graphs are 4-colorable
• 4-coloring \(H\)-free graphs when \(H\) is small
• 4-colorability of P₆-free graphs
• 4-coloring \(H\)-free graphs when \(H\) is small
• Four-coloring \(P_6\)-free graphs

Cites work

• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• A bound on the chromatic number of graphs without certain induced subgraphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Algorithmic graph theory and perfect graphs
• Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• Colouring vertices of triangle-free graphs without forests
• Forbidden subgraphs and 3-colorings
• Polynomial cases for the vertex coloring problem
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• The coloring problem for classes with two small obstructions
• Triangle-free \(2P_3\)-free graphs are 4-colorable
• Vertex coloring of graphs with few obstructions
• Vertex colouring and forbidden subgraphs -- a survey
• \(K_{4}\)-free graphs with no odd holes

Cited in

(8)

• Coloring of a superclass of \(2K_2\)-free graphs
• Chromatic bounds for the subclasses of pK₂-free graphs
• Coloring (\(P_5\), kite)-free graphs with small cliques
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• \(P_4\)-colorings and \(P_4\)-bipartite graphs
• Triangle-free \(2P_3\)-free graphs are 4-colorable
• Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs
• Bounds for the chromatic number of some \(pK_2\)-free graphs

This page was built for publication: \((2P_2,K_4)\)-free graphs are 4-colorable

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