On the Computational Complexity of the Forcing Chromatic Number

DOI10.1137/050641594zbMath1131.68050OpenAlexW2053934832MaRDI QIDQ5454241

Oleg Verbitsky, Wolfgang Slany, Frank Harary

Publication date: 28 March 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.341.8688

zbMATH Keywords

computational complexitycomplexity classesunique satisfiabilitychromatic number of a graphcombinatorial forcing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

This page was built for publication: On the Computational Complexity of the Forcing Chromatic Number