Color class count function equivalence conjecture for partial colorings
Color class count function equivalence conjecture for partial colorings
Let be the graph associated with a node of the smooth tree-decomposition, and let and be partial colorings of . For each tuple in , let denote the number of color classes represented by the tuple, and let denote its color class function. Color class count function equivalence conjecture. If and have the same color class count function, namely
for every , then there is a permutation of the colors such that
for every . The conjecture would allow the algorithm to store color class count functions instead of full color class functions, potentially removing the restriction that the maximum degree is constant and yielding a polynomial-time algorithm.
Sources & referencesView supporting material
Primary source
Yichen Wang and Mei Lu, “A polynomial time algorithm to find star chromatic index on bounded treewidth graphs with given maximum degree”, arXiv:2402.04526 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.