Bounded chromatic number for bounded-degree color classes with no lonely colors
Bounded chromatic number for bounded-degree color classes with no lonely colors
Let be a graph whose edges are colored, and suppose that the subgraph induced by every color has maximum degree . Say that a color is lonely on a cycle if it appears exactly once on that cycle.
No-lonely-color conjecture. There is a function such that, whenever no color is lonely on any cycle of , one has
This conjecture strengthens the no-lonely-color variant of the question discussed in the paper. The supplied status evidence says that the related existence question for graphs with a one popular color coloring remains open; the conjecture itself is therefore recorded as open.
Sources & referencesView supporting material
Primary source
Ignacio García-Marco and Kolja Knauer, “Coloring minimal Cayley graphs”, arXiv:2405.19543 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.