Polynomial-time k-colouring conjecture for graphs with maximal local edge-connectivity k
Statement
Let be fixed, and let be a graph with maximal local edge-connectivity , meaning that the maximum local edge-connectivity over all pairs of vertices of is . A -colouring of is a proper vertex colouring using at most colours.
Polynomial-time k-colouring conjecture. There is a polynomial-time algorithm that, given , finds a -colouring of , or determines that none exists.
The conjecture concerns the unresolved complexity of -colouring for graphs with maximal local edge-connectivity when , following polynomial-time results for narrower connectivity classes and NP-completeness results for related colouring problems.
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.