A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs

DOI10.1016/j.tcs.2023.113936zbMath1528.05021arXiv2212.04659MaRDI QIDQ6039897

Chính T. Hoàng, Ben Cameron

Publication date: 23 May 2023

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

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

zbMATH Keywords

graph colouringcritical graphP5-free graphcertifying algorithmsstructural graph theorygem-free graph

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

• Unnamed Item
• Unnamed Item
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Certifying algorithms
• 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
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 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
• Vertex-critical \((P_5\), banner)-free graphs
• Certifying coloring algorithms for graphs without long induced paths
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Coloring (gem, co‐gem)‐free graphs
• 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
• Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors
• Coloring graphs with no induced five‐vertex path or gem
• Some results on \(k\)-critical \(P_5\)-free graphs

This page was built for publication: A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs