On coloring a class of claw-free graphs.

DOI10.1016/J.ENTCS.2019.08.033MaRDI QIDQ2132368zbMATH OpenOpenAlexWikidataFDO

Authors Yingjun Dai, Angèle M. Foley, Chính T. Hoàng

Publication date 27 April 2022

Full work available at URL https://doi.org/10.1016/j.entcs.2019.08.033

zbMATH Keywords

\(C_4\)-\textit{twin}\(C_5\)-\textit{twin}\(C_6\)-\textit{twin}\(P_5\)-twin\textit{claw}graph coloringhole-twinline-graph

Mathematics Subject Classification ID

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

Recommendations

• On coloring a class of claw-free and hole-twin-free graphs
• Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
• A coloring algorithm for \(4 K_1\)-free line graphs
• On the structure of graphs without claw, \(4K_1\) and co-R
• Characterizations of \((4 K_1,C_4,C_5)\)-free graphs

Cites work

• A coloring algorithm for \(4 K_1\)-free line graphs
• Characterizations of derived graphs
• Clique-width for 4-vertex forbidden subgraphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Handle-rewriting hypergraph grammars
• How To Color Claw-Free Perfect Graphs
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Recognizing Berge graphs
• Recognizing claw-free perfect graphs
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems
• The NP-Completeness of Edge-Coloring
• The strong perfect graph theorem
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Topics on perfect graphs
• Vertex coloring of graphs with few obstructions

Cited in

(14)

• An approximation result for the interval coloring problem on claw-free chordal graphs
• 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
• Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
• Total coloring of claw-free planar graphs
• On the structure of graphs without claw, \(4K_1\) and co-R
• Coloring vertices of claw-free graphs in three colors
• Clique-coloring claw-free graphs
• 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
• scientific article; zbMATH DE number 5179133 (Why is no real title available?)
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• On graphs without four-vertex induced subgraphs
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable

This page was built for publication: On coloring a class of claw-free graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2132368)