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

DOI10.1016/J.TCS.2022.02.009MaRDI QIDQ2124227zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

5-wheelgraph coloringhole-twinpolynomial-time algorithm

Mathematics Subject Classification ID

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

Review text

A hole-twin is the graph obtained from a hole by adding a vertex that forms true twins with some vertex of the hole. A \(5\)-wheel is the graph obtained from a \(C_5\) by adding a vertex that is adjacent to all vertices of the \(C_5\). The authors show that a (\(4K_1\), hole-twin, \(5\)-wheel)-free graph is perfect or has a bounded clique width. As a consequence they obtain a polynomial-time algorithm for the VERTEX COLORING for (\(4K_1\), hole-twin, \(5\)-wheel)-free graphs. This is another class of \(F\)-free graphs for a given set \(F\) of graphs for which there is a polynomial-time algorithm for the VERTEX COLORING problem.

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

Cites work

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

Cited in

(5)

• On coloring a class of claw-free and hole-twin-free graphs
• On coloring a class of claw-free graphs.
• The intersection of two vertex coloring problems
• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs
• On graphs without four-vertex induced subgraphs

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)