Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs

DOI10.1007/s00373-024-02756-xarXiv2306.03376MaRDI QIDQ6121915

Chính T. Hoàng, Ben Cameron

Publication date: 26 March 2024

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

graph colouringcritical graphvertex-critical graph\(P_5\)-free graph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• Some results on graphs without long induced paths
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• 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
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• On $3$-Colorable $P_5$-Free Graphs
• Reducibility among Combinatorial Problems
• Four-coloring P₆-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
• Vertex-critical \((P_5, \mathrm{chair})\)-free graphs
• Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
• Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
• 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

This page was built for publication: Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs