The coloring problem for classes with two small obstructions
From MaRDI portal
Publication:479257
DOI10.1007/s11590-014-0733-yzbMath1308.90189arXiv1307.0278OpenAlexW2020102826MaRDI QIDQ479257
Publication date: 5 December 2014
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.0278
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Coloring of graphs and hypergraphs (05C15)
Related Items (22)
The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ Colouring diamond-free graphs ⋮ The weighted coloring problem for two graph classes characterized by small forbidden induced structures ⋮ The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs ⋮ Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Colouring square-free graphs without long induced paths. ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Polynomial cases for the vertex coloring problem ⋮ Two complexity results for the vertex coloring problem ⋮ Critical hereditary graph classes: a survey ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable ⋮ Colouring square-free graphs without long induced paths ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boundary properties of graphs for algorithmic graph problems
- Some new hereditary classes where graph coloring remains NP-hard
- Colouring vertices of triangle-free graphs without forests
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Boundary classes of graphs for the dominating set problem
- Upper bounds to the clique width of graphs
- NP-hard graph problems and boundary classes of graphs
- Coloring Graphs without Short Cycles and Long Induced Paths
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
- List Coloring in the Absence of Two Subgraphs
- A study of the boundary graph classes for colorability problems
This page was built for publication: The coloring problem for classes with two small obstructions
