On coloring a class of claw-free and hole-twin-free graphs

DOI10.1016/J.DAM.2021.09.034MaRDI QIDQ2091797zbMATH OpenOpenAlexFDO

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

Publication date 2 November 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2021.09.034

zbMATH Keywords

\(P_7\)\textit{claw}graph coloringhole-twinline-graph

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• On coloring a class of claw-free graphs.
• Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
• On the structure of graphs without claw, \(4K_1\) and co-R
• Coloring vertices of claw-free graphs in three colors
• On the structure and clique‐width of (4K1,C4,C6,C7)‐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
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Decomposition by clique separators
• 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 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• On coloring a class of claw-free graphs.
• Recognizing Berge graphs
• Recognizing claw-free perfect graphs
• Reducibility among combinatorial problems
• The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
• The NP-Completeness of Edge-Coloring
• The strong perfect graph theorem
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Three complexity results on coloring \(P_k\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Topics on perfect graphs
• Treewidth. Computations and approximations

Cited in

(4)

• On coloring a class of claw-free graphs.
• Total coloring of claw-free planar graphs
• Coloring vertices of claw-free graphs in three colors
• Clique-coloring claw-free graphs

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

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