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

DOI10.1137/18M1205832zbMATH Open1432.05041arXiv1807.05547MaRDI QIDQ5232143FDOQ5232143

Authors: Serge Gaspers, Shenwei Huang 

Publication date: 29 August 2019

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (8)

• Chromatic bounds for the subclasses of \(pK_2\)-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
• Coloring of a superclass of \(2K_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)