Discrete Mathematics Seminar

Spring 2025

February 12	F. Bailey, URI	Choice Numbers of Graphs: a Probabilistic Approach
		Abstract:    In this seminar we explore key results from the paper Choice Numbers of Graphs: a Probabilistic Approach by Noga Alon. In particular, we will prove there exists a constant $c$, such that the choice number of $K_{m\star r}$ has an upper bound of $s_0=cr\log(m)$. We start with Case 1 where the number of partitions is less than or equal to the number of vertices in each partition, $r\leq m$. Then we will consider Case 2: where the number of partitions is greater than the number of vertices in each partition, $r>m$. This approach gives insights into the probabilistic methods used in the proof and demonstrates how ideas of graph colorings have developed.

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.