The intersection of two vertex coloring problems
From MaRDI portal
Publication:2303434
DOI10.1007/s00373-019-02123-1zbMath1434.05052arXiv1904.08180OpenAlexW2996208793WikidataQ126561496 ScholiaQ126561496MaRDI QIDQ2303434
Dallas J. Fraser, Angèle M. Foley, Kevin Holmes, Tom P. Lamantia, Chính T. Hoàng
Publication date: 3 March 2020
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.08180
Related Items (6)
The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\) ⋮ On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex coloring of graphs with few obstructions
- On rigid circuit graphs
- Topics on perfect graphs
- New graph classes of bounded clique-width
- The strong perfect graph theorem
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Bisimplicial vertices in even-hole-free graphs
- Decomposition by clique separators
- Upper bounds to the clique width of graphs
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- Clique-width for 4-vertex forbidden subgraphs
- Line graphs of bounded clique-width
- Normal hypergraphs and the perfect graph conjecture
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Colouring square-free graphs without long induced paths.
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Characterizations of derived graphs
This page was built for publication: The intersection of two vertex coloring problems
