← All problems

Campos–de Mello total coloring conjecture for powers of cycles

8 years old · traced to

Let CnkC_n^k be the kkth power of the cycle on nn vertices, with 2≤k<⌊n/2⌋2\leq k<\lfloor n/2\rfloor. Its maximum degree is denoted by Δ(Cnk)\Delta(C_n^k), and χ”(Cnk)\chi”(C_n^k) is its total chromatic number.

Campos–de Mello's conjecture. If G=CnkG=C_n^k, then

χ”(G)={Δ(G)+2,if k>n3−1 and n is odd,Δ(G)+1,otherwise.\chi”(G)=\begin{cases} \Delta(G)+2, & \text{if } k>\frac{n}{3}-1 \text{ and } n \text{ is odd},\\ \Delta(G)+1, & \text{otherwise}. \end{cases}

The source states that the total coloring conjecture has been verified for some even-order powers of cycles and that these graphs admit polynomial-time total colorings, while the displayed classification remains presented as a conjecture. The source gives no resolution status for this classification.

References

2 papers in this index state this conjecture (2018–2021). The statement above is taken from the most recent of them; the others are arXiv:1812.05833.

Source: S. Prajnanaswaroopa, J. Geetha and K. Somasundaram, “Total, Equitable Total and Neighborhood sum distinguishing Total Colorings of Some Classes of Circulant Graphs”, arXiv:2105.12490 (2021).

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.