Discrete Mathematics Group at URI

Discrete Mathematics Group at URI

The faculty of our group is interested in a wide range of areas in discrete mathematics both pure and applied: graph theory, network theory, extremal and probabilistic methods, analytic methods, finite model theory, combinatorial games, combinatorial optimization, bioinformatics applications.

Seminar Our seminar is held Fridays 1-2pm, Lippitt 204. Seminar archive.

Speaker Daniel Cranston, Virginia Commonwealth University

Title Proper Conflict-free Coloring of Graphs with Large Maximum Degree

Time Friday November 1, 2024, 1pm, online in zoom (email thoma@math.uri.edu for a link)

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.

News

Discrete Math Day at the University of Rhode Island, September 29, 2018.
Conference announcements at Theorynet, DMANet, and a few other.
Workshop "Non-Combinatorial Combinatorics" will be held at the University of Warwick, 14-16 September 2015, conference webpage.
The 1st Cargese Fall School on Random Graphs will be held in Cargese, Corsica. September 20-25, 2015. Further details can be found at http://math.unice.fr/~dmitsche/Fallschool/Fallschool.html.

Faculty and their research
     Michael Barrus, graph theory
     Nancy Eaton, graph theory
     Barbara Kaskosz, analysis and its applications to discrete mathematics
     William Kinnersley, graph theory and combinatorial games
     Lubos Thoma, extremal and probabilistic combinatorics

Doctoral students
Lilith Wagstrom
John Jones

Graduate courses MTH547 Combinatorics, MTH548 Graph Theory, MTH515/516 Algebra, MTH550 Probability and Stochastic Processes, MTH581 Optimization Methods, MTH656 Probability on Discrete Structures, CSC541 Advanced Topics in Algorithms, CSC542 Mathematical Analysis of Algorithms, CSC544 Theory of Computation, Special topics courses in Extremal Graph Theory, Ramsey Theory, Algebraic Combinatorics.

Discrete mathematics nearby

MIT Combinatorics seminar Brown Combinatorics seminar / applied seminars

MIT Probability seminar Yale Combinatorics and probability seminar

ICERM CMSA

Speaker	Daniel Cranston, Virginia Commonwealth University
Title	Proper Conflict-free Coloring of Graphs with Large Maximum Degree
Time	Friday November 1, 2024, 1pm, online in zoom (email thoma@math.uri.edu for a link)


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.

MIT Combinatorics seminar		Brown Combinatorics seminar / applied seminars
MIT Probability seminar		Yale Combinatorics and probability seminar
ICERM		CMSA