Dominating set based exact algorithms for \(3\)-coloring

DOI10.1016/j.ipl.2010.11.009zbMath1259.05171OpenAlexW1986075609MaRDI QIDQ1944084

C. R. Subramanian, N. S. Narayanaswamy

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.11.009

zbMATH Keywords

graph coloringdesign of algorithmsgraph algorithmsexact algorithms\(3\)-coloringexponential time algorithms

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)

Related Items (1)

Algorithms and almost tight results for 3-colorability of small diameter graphs

Cites Work

• The complexity of colouring problems on dense graphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• A note on the complexity of the chromatic number problem
• Which problems have strongly exponential complexity?
• 3-coloring in time
• On the Hardness of 4-Coloring a 3-Colorable Graph
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Dominating set based exact algorithms for \(3\)-coloring