Strong Coloring Conjecture for the strong chromatic number

About 6 years old · traced to

Let HH be a graph, let Δ(H)\Delta(H) denote its maximum degree, and let schi(H)schi(H) denote its strong chromatic number, the minimum number of colors needed so that every graph formed by adding a clique to the neighborhood of each vertex is properly colorable with those colors. Strong Coloring Conjecture. For any graph HH,

sχ(H)≤2Δ(H).s\chi(H)\leq 2\Delta(H).

The bound would be best possible, since for each maximum degree Δ\Delta there are Δ\Delta-regular graphs with strong chromatic number at least 2Δ2\Delta. The conjecture remains open for all Δ≥2\Delta\geq 2, although several partial results are known for general Δ\Delta.

References

Primary source

Jessica McDonald and Gregory J. Puleo, “Strong coloring 2-regular graphs: Cycle restrictions and partial colorings”, arXiv:2001.05051 (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.