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

computational complexitycomplexity classesunique satisfiabilitychromatic number of a graphcombinatorial forcing

Mathematics Subject Classification ID

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

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

(4)

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

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)