Polynomial cases for the vertex coloring problem
From MaRDI portal
Publication:666663
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
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 P4'S
- Two cases of polynomial-time solvability for the coloring problem
This page was built for publication: Polynomial cases for the vertex coloring problem
