Certifying coloring algorithms for graphs without long induced paths

DOI10.1016/j.dam.2018.09.031zbMath1410.05204arXiv1703.02485OpenAlexW2963705726MaRDI QIDQ2414471

Anna Pstrucha, Marcin Kaminski

Publication date: 17 May 2019

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

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

zbMATH Keywords

obstructionswell-quasi-ordering\(H\)-coloringcoloring algorithms

Mathematics Subject Classification ID

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

Related Items (9)

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 ⋮ Critical \((P_6, \mathrm{banner})\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs ⋮ \(k\)-critical graphs in \(P_5\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of coloring graphs without paths and cycles
• Certifying algorithms
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Graph minors. V. Excluding a planar graph
• On the complexity of H-coloring
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Three complexity results on coloring \(P_k\)-free graphs
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Coloring graphs without short cycles and long induced paths
• Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• The NP-Completeness of Edge-Coloring
• Subgraphs and well‐quasi‐ordering
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Obstructions for three-coloring graphs with one forbidden induced subgraph

This page was built for publication: Certifying coloring algorithms for graphs without long induced paths