ÂÌñÉç

Speaker: Dan Cranston, visiting associate professor of mathematics, College of William and Mary

Title: Proper Conflict-Free Coloring of Graphs with Large Maximum Degree

Abstract:

A proper coloring of a graph is conflict-free if, for every non-isolated vertex, some color is used exactly once on its neighborhood. Caro, Petruševski, and Š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 \(\mathcal{H}\). Our proof uses a fairly new type of recursive counting argument called Rosenfeld counting, which is a variant of the Lovász Local Lemma or entropy compression.

This is joint work with Chun-Hung Liu.

Discrete Applied Math Seminar