Discrete Mathematics Group at URI

Discrete Mathematics Seminar

Spring 2025

March 28 L. Wagstrom, URI The tree-depth and criticality of unicyclic graphs

Abstract: The tree-depth of a graph G is defined as the smallest k for which there exists a proper labeling L of G such that if L(x) = L(y) then every path between x and y must contain a vertex z with L(z) > L(x). The graph G is k-critical if it has tree-depth k and every proper minor of G has tree-depth at most k-1. We investigate when unicyclic graphs are critical. Despite unicyclic graphs' relatively simple structure it is surprisingly difficult to classify when they are critical. Part of this difficulty arises from the large variance of structures in unicyclic graphs. We present several families of critical unicyclic graphs that vary greatly in structure. However, despite the difficulty we will go over a potential classification of critical unicyclic graphs. In addition to these results, we present patterns present in the optimal feasible tree-depth labelings of cycles and general graphs.

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.

Past semesters:

         .                         2024-2025          2023-2024          2022-2023
         2021-2022          2020-2021          2019-2020          2018-2019
         2017-2018          2016-2017          2015-2016          2014-2015
         2013-2014          2012-2013          2011-2012          2010-2011
         2009-2010          2008-2009          2007-2008          2006-2007
         2005-2006          2004-2005          2003-2004          2002-2003

Journals in Discrete Mathematics and related fields

March 28	L. Wagstrom, URI	The tree-depth and criticality of unicyclic graphs
		Abstract: The tree-depth of a graph G is defined as the smallest k for which there exists a proper labeling L of G such that if L(x) = L(y) then every path between x and y must contain a vertex z with L(z) > L(x). The graph G is k-critical if it has tree-depth k and every proper minor of G has tree-depth at most k-1. We investigate when unicyclic graphs are critical. Despite unicyclic graphs' relatively simple structure it is surprisingly difficult to classify when they are critical. Part of this difficulty arises from the large variance of structures in unicyclic graphs. We present several families of critical unicyclic graphs that vary greatly in structure. However, despite the difficulty we will go over a potential classification of critical unicyclic graphs. In addition to these results, we present patterns present in the optimal feasible tree-depth labelings of cycles and general graphs.
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.

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.