\(k\)-critical graphs in \(P_5\)-free graphs

DOI10.1016/j.tcs.2021.02.029zbMath1502.05057arXiv2005.03441OpenAlexW4205858252MaRDI QIDQ5925505

Shenwei Huang, Kathie Cameron, Jan Goedgebeur, Yongtang Shi

Publication date: 8 April 2021

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

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

zbMATH Keywords

graph coloringforbidden induced subgraphsDilworth's theorem\(k\)-critical graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four, A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs, Vertex-critical \((P_5, \mathrm{chair})\)-free graphs, Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs, Critical (\(P_5\), bull)-free graphs, Some results on \(k\)-critical \(P_5\)-free graphs, Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs

Uses Software

• House of Graphs
• CriticalPfreeGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Complexity of coloring graphs without paths and cycles
• Ore's conjecture on color-critical graphs is almost true
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• \(K_{4}\)-free graphs with no odd holes
• Some results on graphs without long induced paths
• Paw-free graphs
• Critical \((P_6, \mathrm{banner})\)-free graphs
• House of Graphs: a database of interesting graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Obstructions for three-coloring graphs without induced paths on six vertices
• Vertex-critical \((P_5\), banner)-free graphs
• Certifying coloring algorithms for graphs without long induced paths
• A decomposition theorem for partially ordered sets
• Note on the colouring of graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• Exhaustive generation of k‐critical ‐free graphs
• On $3$-Colorable $P_5$-Free Graphs
• Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
• A Dual of Dilworth's Decomposition Theorem
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Some Theorems on Abstract Graphs