기초과학연구원 이산수학그룹
On September 22, 2026, David R. Wood from Monash University gave a talk on coloring graphs without K_t minor with t colors while avoiding large monochromatic components at the Discrete Math Seminar. The title of his talk was “Proof of the Clustered Hadwiger Conjecture“.
On September 18, 2026, David R. Wood from Monash University gave a talk showing the proof of the Erdős-Sós conjecture found by GPT Astra at the Discrete Math Seminar. The title of his talk was “The Erdős-Sós Theorem“.
We present an exposition of a proof, discovered by GPT-6 Astra, of the Erdős-Sós Conjecture, which states that every graph with average degree greater than t−2 contains every tree on t≥2 vertices.
Hadwiger famously conjectured that every $K_h$-minor-free graph is properly $(h-1)$-colourable. This talk will present the following improper analogue of Hadwiger’s Conjecture: for fixed $h$, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. This solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed $t\geqslant s$, we show that every $K_{s,t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor, the result is strengthened as follows: for fixed $t \geqslant s \geqslant 3$, and for any fixed apex graph $X$, every $K_{s,t}$-subgraph-free $X$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible. This is joint work with Vida Dujmović, Louis Esperet and Pat Morin [arXiv:2306.06224].
On February 17, 2021, David Wood from Monash University gave an online talk at the Virtual Discrete Math Colloquium on the maximum number of copies of a fixed forest in various sparse graph classes. The title of his talk was “Tree densities of sparse graph classes“.
This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $\mathcal{G}$ as $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular, we show that the answer is $\Theta(n^{\alpha_d(T)})$ where $\alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$, for some integer $d$ that depends on $\mathcal{G}$. For example, when $\mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $\mathcal{G}$ is the class of graphs containing no $K_{s,t}$-minor ($t\geq s$) then $d=s-1$; and when $\mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs. This is joint work with Tony Huynh (arXiv:2009.12989).