Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs

DOI10.1016/j.dam.2023.11.042zbMath1529.05055arXiv2206.03422MaRDI QIDQ6180578

Joe Sawada, Chính T. Hoàng, Tala Abuadas, Ben Cameron

Publication date: 22 December 2023

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

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

zbMATH Keywords

graph coloringcritical graphvertex-critical graphcertifying algorithmgem-free graphco-gem-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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
• Unnamed Item
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Complexity of coloring graphs without paths and cycles
• 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
• Critical \((P_6, \mathrm{banner})\)-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
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• Constructions of \(k\)-critical \(P_5\)-free graphs
• List coloring in the absence of a linear forest
• Vertex-critical \((P_5\), banner)-free graphs
• Certifying coloring algorithms for graphs without long induced paths
• On a property of the class of n-colorable graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• 3-Colorable Subclasses of $P_8$-Free Graphs
• 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
• Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
• Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs
• Four-coloring P₆-free graphs
• \(k\)-critical graphs in \(P_5\)-free graphs
• Vertex-critical \((P_5, \mathrm{chair})\)-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_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs