Seminars

Recent Results on Hamilton-Connected Line Graphs--11/21/23--Dr. Xiaofeng Gu--West Georgia University

Thomassen conjectured that every 4-connected line graph is Hamiltonian.  The best result to date is due to Kaiser and Vrana, who proved that every 5-connected line graph of minimum degree at least 6 is Hamilton-connected. They also proved that every 3-connected essentially 9-connected line graph is Hamilton-connected, where a graph G is essentially k-connected if G has no vertex cut X of size less than k such that G-X has two nontrivial components. Some recent updates and related results will be presented in this talk.

Divisibility Rules--9/22/23--Dr. Jan Zijlstra, Middle Tennessee State University

Division rules can significantly reduce computational efforts in coding theory and related fields.vvEstablishing a simple – if obscure –rule for division by 7, we generalize our proof to generate similar rules for primes up to 200 by (efficient) use of a pocket calculator.  This presentation is aimed at a general audience with an interest in Number Theory. In the process, we discuss proof techniques and extension of existing results.

$\chi$-binding functions for two graph classes--4/21/23--Dr. Zhiyu Wang, Hale Visiting Assistant Professor, in the School of Mathematics, Georgia Institute of Technology

A graph class is called polynomially $\chi$-bounded if there is a function $f$ such that $\chi(G) \leq f(\omega(G))$ for every graph $G$ in this class, where $\chi(G)$ and $\omega(G)$ denote the chromatic number and clique number of $G$ respectively. A \emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing an edge once.  A \emph{fork} is a graph obtained from $K_{1,4}$ by subdividing two edges. We show two conjectures: (1) we show that for graphs $G$ without induced $t$-brooms, $\chi(G) = o(\omega(G)^{t+1})$, answering a question of Schiermeyer and Randerath.  For $t=2$, we strengthen the bound on $\chi(G)$ to $7\omega(G)^2$, confirming a conjecture of Sivaraman. (2) We show that any \{triangle, fork\}-free graph $G$ satisfies $\chi(G)\leq \omega(G)+1$, confirming a conjecture of Randerath. This is joint work with Xiaonan Liu, Joshua Schroeder, and Xingxing Yu.

Spanning Trees in Expanders--4/14/23--Jie Han, Beijing Institute of Technology

We consider the spanning tree embedding problem in dense graphs without bipartite holes and sparse graphs. In 2005, Alon, Krivelevich and Sudakov asked for determining the best possible spectral gap forcing an (n,d,\lambda)-graph to be T(n, \Delta)-universal. In this talk, we introduce our recent work on this conjecture.

Modulo 3-orientation and Sign-circuit covering-- 10/7/22--Dong Ye, MTSU

Minimally Embedding Grid Graphs on Orientable Surfaces--9/30/22--Fabian Salinas, Vanderbilt University

A K-dimensional grid graph is the graph cartesian product of K paths. When the product of K paths includes 3 paths with an odd number of edges, the minimal orientable genus of the corresponding grid graph has been known since 1970 by the work of White. In the unsolved case, the problem becomes non-trivial, as the combinatorial lower bounds provided by White no longer become fruitful. Expanding on Whites work, we classified the minimum orientable genus of 2 infinite families of 3-dimensional grid graphs in the unsolved case. Using visually intuitive methods for constructing orientable surfaces and topological minors, we conjecture an orientable genus formula for any 3-dimensional grid graph that is exact for the families we classified.