Single-conflict colorings of degenerate graphs
This solves a specific graph theory problem for researchers in combinatorial optimization, but it is incremental as it builds on existing work.
The paper addresses the single-conflict coloring problem for degenerate graphs, showing that O(√d log n) colors suffice to avoid forbidden color pairs on edges, answering a prior question from the literature.
We consider the single-conflict coloring problem, a graph coloring problem in which each edge of a graph receives a forbidden ordered color pair. The task is to find a vertex coloring such that no two adjacent vertices receive a pair of colors forbidden at an edge joining them. We show that for any assignment of forbidden color pairs to the edges of a $d$-degenerate graph $G$ on $n$ vertices of edge-multiplicity at most $\log \log n$, $O(\sqrt{ d } \log n)$ colors are always enough to color the vertices of $G$ in a way that avoids every forbidden color pair. This answers a question of DvoÅák, Esperet, Kang, and Ozeki for simple graphs (Journal of Graph Theory 2021).