Polynomial cases for the vertex coloring problem

DOI10.1007/s00453-018-0457-yzbMath1444.68078arXiv1709.07712OpenAlexW2757602845MaRDI QIDQ666663

T. Karthick, Lucas Pastor, Frédéric Maffray

Publication date: 11 March 2019

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsvertex coloring\(P_5\)-free graphstwo forbidden induced subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable ⋮ Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex coloring of graphs with few obstructions
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• The coloring problem for classes with two small obstructions
• Two complexity results for the vertex coloring problem
• On the structure of bull-free perfect graphs
• On algorithms for (\(P_5\), gem)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Bull-free Berge graphs are perfect
• Zero knowledge and the chromatic number
• Modular decomposition and transitive orientation
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Recognizing bull-free perfect graphs
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Solving the clique cover problem on (bull, \(C_4\))-free graphs
• Recognizing Berge graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Improved Complexity Results on k-Coloring P t -Free Graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Four classes of perfectly orderable graphs
• Graph Classes: A Survey
• On the hardness of approximating minimization problems
• Reducibility among Combinatorial Problems
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• Two cases of polynomial-time solvability for the coloring problem

This page was built for publication: Polynomial cases for the vertex coloring problem