Vertex-critical \((P_5, \mathrm{chair})\)-free graphs

DOI10.1016/j.dam.2023.07.014zbMath1526.05050arXiv2301.02436OpenAlexW4385678927MaRDI QIDQ6069143

Zeyu Li, Shenwei Huang

Publication date: 13 November 2023

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

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

zbMATH Keywords

graph coloringforbidden induced subgraphs\(k\)-vertex-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 (2)

Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs

Cites Work

• Unnamed Item
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Complexity of coloring graphs without paths and cycles
• Critical \((P_6, \mathrm{banner})\)-free graphs
• Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Vertex-critical \((P_5\), banner)-free graphs
• Certifying coloring algorithms for graphs without long induced paths
• \(k\)-critical graphs in \(P_5\)-free graphs
• Critical (\(P_5\), bull)-free graphs
• Some results on \(k\)-critical \(P_5\)-free graphs

This page was built for publication: Vertex-critical \((P_5, \mathrm{chair})\)-free graphs