$(2P_2,K_4)$-Free Graphs are 4-Colorable
From MaRDI portal
Publication:5232143
DOI10.1137/18M1205832zbMath1432.05041arXiv1807.05547MaRDI QIDQ5232143
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
Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ 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 ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques
Cites Work
- Vertex coloring of graphs with few obstructions
- The coloring problem for classes with two small obstructions
- Polynomial cases for the vertex coloring problem
- Colouring vertices of triangle-free graphs without forests
- \(K_{4}\)-free graphs with no odd holes
- A bound on the chromatic number of graphs without certain induced subgraphs
- Coloring the hypergraph of maximal cliques of a graph with no long path
- Algorithmic graph theory and perfect graphs
- Vertex colouring and forbidden subgraphs -- a survey
- Triangle-free \(2P_3\)-free graphs are 4-colorable
- The chromatic number of \(\{P_5,K_4\}\)-free graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- Forbidden Subgraphs and 3-Colorings
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: $(2P_2,K_4)$-Free Graphs are 4-Colorable
