Georgia Institute of Technology College of Sciences

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 (resp. sum-distinguishing) edge-$k$-coloring of $G$ is an edge-$k$-coloring such that for any two distinct vertices $u$ and $v$, the set (resp. sum) 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 (resp. sum-distinguishing chromatic index), denoted $\chi'_{vd}(G)$ (resp.  $\chi'_{sd}(G)$), is the smallest value $k$ such that $G$ has a vertex-distinguishing edge-$k$-coloring (resp. sum-distinguishing edge-$k$-coloring). Let $G$ be a   $d$-regular graph on $n$ vertices, where $n$ is even and sufficiently large. We show that $\chi'_{vd}(G) =d+2$ if $d$ is arbitrarily close to $n/2$ from above, and $\chi'_{sd}(G) =d+2$ if $d\ge \frac{2n}{3}$. 

This is joint work with Yuping Gao and Guanghui Wang.

We discuss the recent progress on Graham's Conjecture which states that for any subset $S \subseteq \mathbb{Z}_p \setminus \{0\}$, there exists an ordering of the elements $s_1, \cdots, s_m$ of $S$ such that the partial sums $\sum_{i = 1}^k s_i$ are all distinct. This was very recently proven for all sufficiently large primes by Pham and Sauermann, however our work focuses on the more general setting where $\mathbb{Z}_p$ is replaced by an arbitrary finite group, where the result is also conjectured to hold.

By considering the Cayley Graph, we can translate the problem into the purely graph theoretic problem of finding a rainbow path of length $d - 1$ in any $d$-regular properly edge-colored directed graph. We give an asymptotic result which builds on work by Bucić, Frederickson, Müyesser, Pokrovskiy, and Yepremyan, and shows that we can find a path of length $(1 - o(1)) d$. This corresponds to showing that for any subset $S \subseteq G$, there exists a dense subset $S' \subseteq G$ and an ordering $s'_1, \cdots, s'_m$ of the elements of $S'$ such that the partial products $\prod_{i  = 1}^k s'_i$ are all distinct.

A simple algorithm for computing the diameter of an unweighted $n$-vertex graph is to run a BFS from every vertex of the graph. This leads to quadratic time algorithms for computing diameter in sparse graphs and geometric intersection graphs. There are matching fine-grained lower bounds which show that in many cases, it is not possible to get a truly subquadratic time algorithm for diameter computation.

To contrast, we give the first truly subquadratic time algorithm for computing the diameter of an $n$-vertex unit-disk graph. The algorithm runs in with $O^*(n^{2-1/18})$ time. The result is obtained as an instance of a general framework, applicable for distance problems in any graph with bounded distance VC-dimension. To obtain these results, we exploit bounded VC-dimension of neighborhood balls,  low-diameter decompositions, and geometric data structures.

Based on paper in FOCS 2025, joint work with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, and Hung Le. Arxiv: https://arxiv.org/abs/2510.16346

A graph is chordal if each of its cycles of length at least four has a chord. Chordal graphs occupy an extreme end of a trade-off between structure and generalization: they have strong structure and admit many interesting characterizations, but this strong structure makes them a special case, representative of only a few graphs. In this talk, I'll discuss a new class of graphs called locally chordal graphs. Locally chordal graphs are more general than chordal graphs, but still have enough structure to admit interesting characterizations. In particular, most of the major characterizations of chordal graphs generalize to locally chordal graphs in natural and powerful ways. In addition to explaining these characterizations, I’ll discuss some ideas about how locally chordal graphs relate to new width parameters and to results in structural sparsity. This talk is based on joint work with Paul Knappe and Jonas Kobler.