Tag: AmadeusReinald

In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1{)}^2$ suffices, which was improved in 2013 to $\frac{k^2}{2}–\frac{k}{2}+1$ by Addario-Berry et al.

In this talk, we give the first subquadratic bound for Burr’s conjecture, by showing that every directed graph with chromatic number $8\sqrt{\frac{2}{15}}k\sqrt{k}+O(k)$ contains any oriented tree of order $k$. Moreover, we provide improved bounds of $\sqrt{\frac{4}{3}}k\sqrt{k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$.

Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided with a sequence witnessing the bound. Classes of bounded twin-width are very diverse, notably including bounded rank-width, $\mathrm{\Omega }(\log (n))$-subdivisions of graphs of size $n$, and proper minor closed classes. In this talk, we look at developing a structural understanding of twin-width in terms of induced subdivisions.

Structural characterizations of graph parameters have mostly looked at graph minors, for instance, bounded tree-width graphs are exactly those forbidding a large wall minor. An analogue in terms of induced subgraphs could be that, for sparse graphs, large treewidth implies the existence of an induced subdivision of a large wall. However, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2,3}$). Abrishami, Chudnovsky, Hajebi and Spirkl have recently shown that such (theta, triangle)-free classes have nevertheless logarithmic treewidth.

After an introduction to twin-width and its ties to vertex orderings, we show that theta-free graphs of girth at least 5 have bounded twin-width.

Joint work with Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant.