Two complexity results for the vertex coloring problem

DOI10.1016/j.dam.2016.10.025zbMath1440.05093OpenAlexW2560576235MaRDI QIDQ505438

O. O. Lobanova, Dmitriy S. Malyshev

Publication date: 23 January 2017

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

Full work available at URL: https://doi.org/10.1016/j.dam.2016.10.025

zbMATH Keywords

computational complexitypolynomial-time algorithmhereditary classcoloring problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (13)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ The weighted coloring problem for two graph classes characterized by small forbidden induced structures ⋮ 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 ⋮ Colouring square-free graphs without long induced paths. ⋮ Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Coloring graphs without induced \(P_5\) or \(K_5-e\) ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Polynomial cases for the vertex coloring problem ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex coloring of graphs with few obstructions
• Edge-colouring and total-colouring chordless graphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Coloring graphs characterized by a forbidden subgraph
• The coloring problem for classes with two small obstructions
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Boundary properties of graphs for algorithmic graph problems
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Colouring vertices of triangle-free graphs without forests
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The strong perfect graph theorem
• The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
• Decomposition by clique separators
• 4-coloring \(H\)-free graphs when \(H\) is small
• Vertex colouring and forbidden subgraphs -- a survey
• Three complexity results on coloring \(P_k\)-free graphs
• Chromatic index of graphs with no cycle with a unique chord
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Complexity separating classes for edge-colouring and total-colouring
• NP-hard graph problems and boundary classes of graphs
• On the complexity of 4-coloring graphs without long induced paths
• Recognizing Berge graphs
• On the number of boundary classes in the 3-colouring problem
• Graph colorings with local constraints -- a survey
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
• Paths, Trees, and Flowers
• Transitiv orientierbare Graphen
• Two cases of polynomial-time solvability for the coloring problem

This page was built for publication: Two complexity results for the vertex coloring problem