Coloring \((4K_1,C_4,C_6)\)-free graphs

DOI10.1016/j.disc.2022.113225zbMath1527.05073OpenAlexW4307571145MaRDI QIDQ6091816

Irena Penev

Publication date: 27 November 2023

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

Full work available at URL: https://doi.org/10.1016/j.disc.2022.113225

zbMATH Keywords

graph coloringmaximal cliqueseven-hole-free graphsminimum clique cover\((4K_1,C_4,C_6)\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Cites Work

• On rigid circuit graphs
• The strong perfect graph theorem
• Triangulated neighborhoods in even-hole-free graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• On diameters and radii of bridged graphs
• Geometric algorithms and combinatorial optimization
• Efficient graph representations
• On simplicial and co-simplicial vertices in graphs.
• Structure and algorithms for (cap, even hole)-free graphs
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• The intersection of two vertex coloring problems
• A faster algorithm to recognize even-hole-free graphs
• Incidence matrices and interval graphs
• Recognizing Berge graphs
• A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\)
• Even-hole-free graphs part I: Decomposition theorem
• Even-hole-free graphs part II: Recognition algorithm
• Algorithmic Aspects of Vertex Elimination on Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Clique-width III
• Algorithm Theory - SWAT 2004
• Clique‐cutsets beyond chordal graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Coloring rings
• On the structure and clique‐width of (4K1,C4,C6,C7)‐free graphs

This page was built for publication: Coloring \((4K_1,C_4,C_6)\)-free graphs