Bounded chromatic number for bounded-degree color classes with no lonely colors

Let GG be a graph whose edges are colored, and suppose that the subgraph induced by every color has maximum degree dd. 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 ff such that, whenever no color is lonely on any cycle of GG, one has

χ(G)f(d).\chi(G)\leq f(d).

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

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.