The complexity dichotomy conjecture for backbone coloring of degree-4 graphs
Statement
Let be a graph with maximum degree , let , and let be a backbone. For an integer , denotes the -backbone coloring problem with at most colors. Backbone coloring complexity conjecture. For any when is a matching or a galaxy, or when is a Hamiltonian path or a spanning tree, the problem is either trivial, meaning that the answer is YES for all graphs, or -complete. This conjecture proposes a uniform complexity description for fixed maximum degree four, while the cases for galaxy, path, and tree backbones that are not covered by known results remain open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.