On coloring a class of claw-free graphs.

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

zbMATH Keywords

graph coloringline-graph\textit{claw}hole-twin\(C_4\)-\textit{twin}\(C_5\)-\textit{twin}\(C_6\)-\textit{twin}\(P_5\)-twin

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

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.