Vertex coloring (4K₁, hole-twin, 5-wheel)-free graphs

DOI10.1016/J.TCS.2022.02.009zbMATH Open1493.68263OpenAlexW4212817891MaRDI QIDQ2124227FDOQ2124227

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

Publication date: 19 April 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.02.009

Recommendations

• A coloring algorithm for \(4 K_1\)-free line graphs
• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs
• Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
• On the structure of graphs without claw, \(4K_1\) and co-R

zbMATH Keywords

graph coloringpolynomial-time algorithmhole-twin5-wheel

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Title not available (Why is that?)
• Vertex coloring of graphs with few obstructions
• Characterizations of derived graphs
• The strong perfect graph theorem
• Recognizing Berge graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Clique-width for 4-vertex forbidden subgraphs
• Topics on perfect graphs
• On coloring a class of claw-free graphs.
• Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
• A coloring algorithm for \(4 K_1\)-free line graphs

Cited In (1)

• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs

This page was built for publication: Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs

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