The odd chromatic number conjecture for connected graphs

About 4 years old · traced to

Let GG be a connected graph with maximum degree Δ≥3\Delta\geq3. A proper coloring of GG is odd if, for every non-isolated vertex vv, some color appears an odd number of times in the open neighborhood N(v)N(v); write χo(G)\chi_o(G) for the minimum number of colors in an odd coloring.

Odd chromatic number conjecture. If GG is a connected graph of maximum degree Δ≥3\Delta\geq3, then

χo(G)≤Δ+1.\chi_o(G)\leq\Delta+1.

This conjecture was previously proposed in connection with the odd chromatic number, a parameter satisfying χ(G)≤χo(G)≤χpcf(G)\chi(G)\leq\chi_o(G)\leq\chi_{\rm pcf}(G). Its resolution is not given in the supplied text.

References

Primary source

Yair Caro, Mirko Petruševski and Riste Škrekovski, “Remarks on proper conflict-free colorings of graphs”, arXiv:2203.01088 (2022).

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.