473 citations · 2k across the 152 of their papers we have counts for
14 papers · 1 filter
Nonrepetitive Colouring via Entropy Compression
Vida Dujmović, Gwenaël Joret, Jakub Kozik +1
A vertex colouring of a graph is \emph{nonrepetitive} if there is no path whose first half receives the same sequence of colours as the second half. A graph is nonrepetitively -…
An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
Vida Dujmović, Gwenaël Joret, David R. Wood
It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particula…
Disproof of the List Hadwiger Conjecture
János Barát, Gwenaël Joret, David R. Wood
The List Hadwiger Conjecture asserts that every -minor-free graph is -choosable. We disprove this conjecture by constructing a -minor-free graph that is not -…
Colouring the Triangles Determined by a Point Set
Ruy Fabila-Monroy, David R. Wood
Let P be a set of n points in general position in the plane. We study the chromatic number of the intersection graph of the open triangles determined by P. It is known that this ch…
Nordhaus-Gaddum for Treewidth
Gwenaël Joret, David R. Wood
We prove that for every graph with vertices, the treewidth of plus the treewidth of the complement of is at least . This bound is tight.
Decompositions of Complete Multipartite Graphs into Complete Graphs
Ruy Fabila-Monroy, David R. Wood
Let and be integers. Let be the complete -partite graph with vertices in each colour class. An -decomposition of is a set…