3-colouring \(P_t\)-free graphs without short odd cycles

DOI10.1007/s00453-022-01049-0OpenAlexW4306655159MaRDI QIDQ2696271

Alberto Rojas Anríquez, Maya Jakobine Stein

Publication date: 11 April 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

algorithmgraphcolouring3-colouringforbidden subgraph\(P_t\)-free

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of coloring graphs without paths and cycles
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The ellipsoid method and its consequences in combinatorial optimization
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Three complexity results on coloring \(P_k\)-free graphs
• Colouring \((P_r + P_s)\)-free graphs
• Better 3-coloring algorithms: excluding a triangle and a seven vertex path
• List coloring in the absence of a linear forest
• Coloring graphs without short cycles and long induced paths
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• The NP-Completeness of Edge-Coloring
• 3-Colorable Subclasses of $P_8$-Free Graphs
• NP completeness of finding the chromatic index of regular graphs
• Reducibility among Combinatorial Problems

This page was built for publication: 3-colouring \(P_t\)-free graphs without short odd cycles