Strong Coloring Conjecture for the strong chromatic number
Strong Coloring Conjecture for the strong chromatic number
Let be a graph, let denote its maximum degree, and let 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 ,
The bound would be best possible, since for each maximum degree there are -regular graphs with strong chromatic number at least . The conjecture remains open for all , although several partial results are known for general .
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
Sign in to submit a solution.
No solutions have been posted yet.