Strong Coloring Conjecture for the strong chromatic number

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

Jessica McDonald and Gregory J. Puleo, “Strong coloring 2-regular graphs: Cycle restrictions and partial colorings”, arXiv:2001.05051 (2021).

Solutions 0

No solutions have been posted yet.