Discrete Mathematics Seminar

Spring 2025

Fall 2024

November 1	D. Cranston, Virginia Commonwealth University	Proper Conflict-free Coloring of Graphs with Large Maximum Degree
		Abstract:    A proper coloring of a graph is \emph{conflict-free} if, for every non-isolated vertex, some color is used exactly once on its neighborhood. Caro, Petru\v{s}evski, and \v{S}krekovski proved that every graph $G$ has a proper conflict-free coloring with at most $5\Delta(G)/2$ colors and conjectured that $\Delta(G)+1$ colors suffice for every connected graph $G$ with $\Delta(G)\ge 3$. Our first main result is that even for list-coloring, $\left\lceil1.6550826\Delta(G)+\sqrt{\Delta(G)}\right\rceil$ colors suffice for every graph $G$ with $\Delta(G)\ge 10^{8}$; we also prove slightly weaker bounds for all graphs with $\Delta(G)\ge 750$. These results follow from our more general framework on proper conflict-free list-coloring of a pair consisting of a graph $G$ and a ``conflict'' hypergraph $H$. Our proof uses a fairly new type of recursive counting argument called Rosenfeld counting, which is a variant of the Lov\'{a}sz Local Lemma or entropy compression. This is joint work with Chun-Hung Liu.