On coloring a class of claw-free graphs.
From MaRDI portal
Publication:2132368
DOI10.1016/j.entcs.2019.08.033OpenAlexW2978207776WikidataQ113317399 ScholiaQ113317399MaRDI QIDQ2132368
Chính T. Hoàng, Angèle M. Foley, Yingjun Dai
Publication date: 27 April 2022
Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.033
graph coloringline-graph\textit{claw}hole-twin\(C_4\)-\textit{twin}\(C_5\)-\textit{twin}\(C_6\)-\textit{twin}\(P_5\)-twin
Related Items (7)
Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs ⋮ The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ On the structure of graphs without claw, \(4K_1\) and co-R ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ On coloring a class of claw-free and hole-twin-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Vertex coloring of graphs with few obstructions
- Topics on perfect graphs
- The strong perfect graph theorem
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Recognizing claw-free perfect graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- Some simplified NP-complete graph problems
- A coloring algorithm for \(4 K_1\)-free line graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- Handle-rewriting hypergraph grammars
- Clique-width for 4-vertex forbidden subgraphs
- Recognizing Berge graphs
- The NP-Completeness of Edge-Coloring
- How To Color Claw-Free Perfect Graphs
- Reducibility among Combinatorial Problems
- Characterizations of derived graphs
This page was built for publication: On coloring a class of claw-free graphs.
