Approximately coloring graphs without long induced paths

DOI10.1007/978-3-319-68705-6_15zbMath1483.05177arXiv1606.02967OpenAlexW3022235449WikidataQ127962562 ScholiaQ127962562MaRDI QIDQ5915792

Sophie Spirkl, Oliver Schaudt, Mingxian Zhong, Maria Chudnovsky, Maya Jakobine Stein

Publication date: 4 January 2018

Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmgraph coloringforbidden induced paths

Mathematics Subject Classification ID

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

Related Items (4)

New formulations and branch-and-cut procedures for the longest induced path problem ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Unnamed Item ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The complexity of colouring problems on dense graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Coloring 3-colorable graphs with o(n 1/5 ) colors
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Conditional Hardness for Approximate Coloring
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• Reducibility among Combinatorial Problems
• Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs
• New hardness results for graph and hypergraph colorings

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