Color class count function equivalence conjecture for partial colorings

Let GiG_i' be the graph associated with a node XiX_i of the smooth tree-decomposition, and let ff and gg be partial colorings of GiG_i'. For each tuple (A(j))1j9\big( A^{(j)} \big)_{1 \le j \le 9} in S(Xi)\mathcal{S}(X_i), let CFf((A(j))1j9)CF_f\left(\big( A^{(j)} \big)_{1 \le j \le 9}\right) denote the number of color classes represented by the tuple, and let CLf((A(j))1j9)CL_f\left(\big( A^{(j)} \big)_{1 \le j \le 9}\right) denote its color class function. Color class count function equivalence conjecture. If ff and gg have the same color class count function, namely

CFf((A(j))1j9)=CFg((A(j))1j9)CF_f\left(\big( A^{(j)} \big)_{1 \le j \le 9}\right)=CF_g\left(\big( A^{(j)} \big)_{1 \le j \le 9}\right)

for every (A(j))1j9S(Xi)\big( A^{(j)} \big)_{1 \le j \le 9}\in\mathcal{S}(X_i), then there is a permutation π\pi of the colors such that

CLπf((A(j))1j9)=CLg((A(j))1j9)CL_{\pi\circ f}\left(\big( A^{(j)} \big)_{1 \le j \le 9}\right)=CL_g\left(\big( A^{(j)} \big)_{1 \le j\le 9}\right)

for every (A(j))1j9S(Xi)\big( A^{(j)} \big)_{1 \le j \le 9}\in\mathcal{S}(X_i). 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 Δ\Delta 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.