Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs

DOI10.1007/978-3-662-53536-3_10zbMath1417.05066arXiv1506.03647OpenAlexW2245397833MaRDI QIDQ3181051

Jan Goedgebeur, Oliver Schaudt

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.03647

zbMATH Keywords

graph coloringcritical graph\(H\)-free graphgraph generation

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Dynamic \(F\)-free coloring of graphs, Computational aspects of greedy partitioning of graphs, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

Uses Software

• nauty
• House of Graphs
• Traces
• CriticalPfreeGraphs

Cites Work

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• House of Graphs: a database of interesting graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Practical graph isomorphism. II.
• Coloring graphs without short cycles and long induced paths
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Isomorph-Free Exhaustive Generation
• Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• NP completeness of finding the chromatic index of regular graphs
• On $3$-Colorable $P_5$-Free Graphs
• Complexity of Coloring Graphs without Paths and Cycles
• Unnamed Item
• Unnamed Item
• Unnamed Item