On the Computational Complexity of the Forcing Chromatic Number

DOI10.1137/050641594MaRDI QIDQ5454241zbMATH OpenOpenAlexFDO

Authors Wolfgang Slany, Oleg Verbitsky, 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

chromatic number of a graphcombinatorial forcingcomplexity classescomputational complexityunique satisfiability

Mathematics Subject Classification ID

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

Recommendations

• STACS 2005
• On the complexity of failed zero forcing
• Some results concerning the complexity of restricted colorings of graphs
• Complexity and computation of connected zero forcing
• On the total forcing number of a graph

Cited in

(5)

• STACS 2005
• Bounds and monotonicity of critical set parameters of colourings
• Hardness of pre-assignment problem for unique minimum vertex cover on planar graphs with maximum degree 3
• The complexity of pre-assignment problem for unique minimum vertex cover on bipartite graphs
• Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs

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

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