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

DOI10.1016/j.dam.2021.09.034OpenAlexW3210518392MaRDI QIDQ2091797

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

graph coloringline-graph\(P_7\)\textit{claw}hole-twin

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Topics on perfect graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Decomposition by clique separators
• Recognizing claw-free perfect graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Treewidth. Computations and approximations
• A coloring algorithm for \(4 K_1\)-free line graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Three complexity results on coloring \(P_k\)-free graphs
• On coloring a class of claw-free graphs.
• 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
• The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness
• Characterizations of derived graphs