Combinatorics Seminars
Feb 11, 2026 01:00 PM
ZOOM
Speaker: Gexin Yu (William & Mary)
Title: Routing in cycles via matchings
Abstract: Let \(G\) be a graph whose vertices are labeled \(1,\ldots,n\), and \(\pi\) be a permutation on \([n] := \{1,2,\ldots,n\}\). A pebble \(p_i\) that is initially placed at the vertex \(i\) has destination \(\pi(i)\) for each \(i \in [n]\). At each step, we choose a matching and swap the two pebbles on each of the edges. Let \(rt(G,\pi)\), the routing number for \(\pi\), be the minimum number of steps necessary for the pebbles to reach their destinations. Li, Lu, and Yang proved that \(rt(C_n,\pi)\leq n-1\) for every permutation \(\pi\) on the \(n\)-cycle \(C_n\) and conjectured that for \(n \geq 5\), if \(rt(G,\pi)= n-1\), then \(\pi=(123\cdots n)\) or its inverse. He, Valentin, Yin, and Yu proved the conjecture for all even \(n \geq 6\). In this talk we will show how to prove the entire conjecture.
This is joint work with Xiangjun Li and Xia Zhang.
Feb 04, 2026 01:00 PM
328 Parker Hall
Speaker: Sam Spiro (Georgia State University)
Title: The Small Quasikernel Conjecture
DMS Combinatorics Seminar
Jan 28, 2026 01:00 PM
ZOOM
Speaker: Yuping Gao (Lanzhou University)
Title:Vertex-distinguishing edge coloring of graphs
Abstract: Given an integer \(k\ge1\), an edge-\(k\)-coloring of a graph \(G\) is an assignment of \(k\) colors \(1,\ldots,k\) to the edges of \(G\) such that no two adjacent edges receive the same color. A vertex-distinguishing edge-\(k\)-coloring of \(G\) is an edge-\(k\)-coloring such that for any two distinct vertices \(u\) and \(v\), the set of colors taken from all the edges incident with \(u\) is different from that taken from all the edges incident with \(v\). The vertex-distinguishing chromatic index, denoted \(\chi'_{vd}(G)\), is the smallest value \(k\) such that \(G\) has a vertex-distinguishing edge-\(k\)-coloring. In this talk, we present some recent progress on vertex-distinguishing edge colorings.
This work is joint with Songling Shan, Guanghui Wang, and Yiming Zhou.
DMS Combinatorics Seminar
Jan 21, 2026 01:00 PM
328 Parker Hall
Speaker: Guantao Chen (Georgia State University)
Title: Adjacent cubic vertices in a minimal brick
Abstract: A connected graph \(G\) is called a matching covered graph if \(E(G)\neq\emptyset\) and every edge of \(G\) lies in a perfect matching, that is, a matching covering all vertices of \(G\). A matching covered graph is said to be bicritical if, for any two distinct vertice \(x,y\in V(G)\), the graph \(G-x-y\) has a perfect matching. A brick is a 3-connected bicritical graph, and it is minimal if the deletion of any edge destroys this property. A well-known conjecture of Lov\'asz asserts that every minimal brick contains two adjacent cubic (degree-3) vertices.
In this talk, we present progress toward Lovász’s conjecture and establish several partial results. In particular, we show that every minimal brick contains two cubic vertices at distance at most two. We also verify the conjecture for minimal bricks with average degree at least \(4.5\). As a consequence, we deduce that every minimal brick contains two adjacent vertices of degree at most five.DMS Combinatorics Seminar
Jan 14, 2026 01:00 PM
ZOOM
Speaker: Abhishek Dhawan (University of Illinois Urbana-Champaign)
Title: A survey of near-Vizing edge-coloring
This talk is partially based on joint work with Anton Bernshteyn.
DMS Combinatorics Seminar
Nov 19, 2025 02:00 PM
ZOOM
Speaker: Noga Alon (Princeton University)
Title: Vantage Points and Sign Patterns
Abstract: Motivated by a possible application in Social Choice, I will discuss a recent work with Defant, Kravitz and Zhu that studies the number of ways to order points in the plane or in higher dimension according to the sum of their (Euclidean) distances from chosen vantage points.
A crucial mathematical tool here is an extension of results of Milnor and Warren about sign patterns of real polynomials, that have been used in the study of several problems in Discrete Mathematics and theoretical Computer Science, to a version that deals with sign patterns of more general functions.
DMS Combinatorics Seminar
Nov 12, 2025 02:00 PM
328 Parker Hall
Speaker: Xiaofan Yuan (Arizona State University)
Title: Tight minimum colored degree condition for rainbow connectivity
Abstract: Let \(G = (V, E)\) be a graph on \(n\) vertices, and let \(c : E \to P\), where \(P\) is a set of colors. Let \(\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}\) where \(d^c(v)\) is the number of colors on edges incident to a vertex \(v\) of \(G\). In 2011, Fujita and Magnant showed that if \(G\) is a graph on \(n\) vertices that satisfies \(\delta^c(G)\geq n/2\), then for every two vertices \(u, v\) there is a properly-colored \(u,v\)-path in \(G\). We show that for sufficiently large graphs \(G\) the same bound for \(\delta^c(G)\) implies that any two vertices are connected by a rainbow path.
This is joint work with Andrzej Czygrinow.
DMS Combinatorics Seminar
Nov 05, 2025 01:00 PM
328 Parker Hall
Title: Maximum in-general-position set in a random subset of \(\mathbb{F}_q^d\)
DMS Combinatorics Seminar
Oct 29, 2025 02:00 PM
ZOOM
Speaker: Michael Santana (Grand Valley State University, Allendale, Michigan)
Title: Sharpening and extending results on disjoint cycle structures
Abstract: In 1963, Corrádi and Hajnal verified a conjecture of Erdős by showing that for every \(k \in \mathbb{Z}\), if an \(n\)-vertex graph \(G\) satisfies \(n \ge 3k\) and \(\delta(G) \ge 2k\), then \(G\) will contain \(k\) disjoint cycles. This result is extremely tight and has served as the motivation behind a great deal of research in recent years. In this talk, we will discuss only a few of these extensions with an emphasis on their sharpness. Time permitting, we will also talk about recent extensions into hypergraphs.
Variety of the work mentioned is joint with Emily Marshall, Theodore Molla, and Elyse Yeager.
DMS Combinatorics Seminar
Oct 22, 2025 02:00 PM
328 Parker Hall
Speaker: Ariel Cook (Auburn University)
Title: Graph-Referential Colorings of Graphs
Abstract: Let \(G\) and \(H\) be finite, simple graphs on the same vertex set \(V\). A proper \(G\)-coloring of \(H\) is a proper list-coloring of \(H\) from the lists \(N_G(v)\), the open neighborhood of \(v \in V(G)\).
If a \(G\)-coloring of \(H\) exists, then we say that \(H\) is \(G\)-colorable. Further, we define a graph \(H\) to be maximally-\(G\)-colorable if \(H\) is \(G\)-colorable and for any edge \(e \in \overline{E(H)}\), \(H \cup e\) is not \(G\)-colorable. Similarly, we define a graph \(H\) to be minimally-not-\(G\)-colorable if \(H\) is not \(G\)-colorable and for any edge \(e \in E(H)\), \(H - e\) is \(G\)-colorable.
In this talk, we will discuss recent results regarding maximally-\(G\)-colorable graphs \(H\) and minimally-not-\(G\)-colorable graphs \(H\).
This is joint work with Dr. Peter Johnson and Dr. Joseph Briggs.
DMS Combinatorics Seminar
Oct 15, 2025 02:00 PM
328 Parker Hall
Speaker: Owen Henderschedt (Auburn University)
Title: List-orientations and total-coloring extensions of planar graphs
In this talk, I will discuss two problems in graph theory. I will briefly consider the first, which concerns finding orientations that satisfy prescribed out-degree restrictions. The second focuses on coloring extensions, asking when a graph with some precolored subgraphs can be totally colored without introducing additional colors. Inspired by vertex- and edge-coloring extension problems, we initiate the study of total-coloring extensions, proposing several conjectures and proving them for planar graphs.
This is joint work with Jessica McDonald.