Two cases of polynomial-time solvability for the coloring problem

DOI10.1007/S10878-014-9792-3zbMATH Open1333.05120OpenAlexW2124367257MaRDI QIDQ5963654FDOQ5963654

D. S. Malyshev

Publication date: 23 February 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-014-9792-3

Recommendations

• Polynomial cases for the vertex coloring problem
• The coloring problem for classes with two small obstructions
• Polynomial-time approximation algorithms for the coloring problem in some cases
• scientific article; zbMATH DE number 2044943
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs

zbMATH Keywords

computational complexitypolynomial-time algorithmvertex coloring

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Sur le coloriage des graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Vertex coloring of graphs with few obstructions
• Title not available (Why is that?)
• The coloring problem for classes with two small obstructions
• Boundary properties of graphs for algorithmic graph problems
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Title not available (Why is that?)
• Some new hereditary classes where graph coloring remains NP-hard
• Colouring of graphs with Ramsey-type forbidden subgraphs
• List Coloring in the Absence of Two Subgraphs
• Colouring vertices of triangle-free graphs without forests
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs

Cited In (26)

• Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem
• Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions
• Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• Deciding Relaxed Two-Colourability: A Hardness Jump
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions
• Colouring square-free graphs without long induced paths.
• Colouring square-free graphs without long induced paths
• Colouring diamond-free graphs
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Critical hereditary graph classes: a survey
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• The chromatic number of (\(P_5\), HVN)-free graphs
• Coloring graphs without induced \(P_5\) or \(K_5-e\)
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• Title not available (Why is that?)
• Two complexity results for the vertex coloring problem
• Non-perfect \((P_5, C_5, K_5 -e)\)-free graphs are 5-colorable
• Polynomial cases for the vertex coloring problem
• Divisibility and coloring of some \(P_5\)-free graphs
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs

This page was built for publication: Two cases of polynomial-time solvability for the coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963654)