This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble methods. We also give a detailed sketch of some aspects of the recent proof of the ErdH{o}s-Faber-Lov{a}sz conjecture.
The ErdH{o}s-Faber-Lov{a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stabili
We propose a new generative model for layout generation. We generate layouts in three steps. First, we generate the layout elements as nodes in a layout graph. Second, we compute constraints between layout elements as edges in the layout graph. Third
, we solve for the final layout using constrained optimization. For the first two steps, we build on recent transformer architectures. The layout optimization implements the constraints efficiently. We show three practical contributions compared to the state of the art: our work requires no user input, produces higher quality layouts, and enables many novel capabilities for conditional layout generation.
We initiate a systematic study of the fractional vertex-arboricity of planar graphs and demonstrate connections to open problems concerning both fractional coloring and the size of the largest induced forest in planar graphs. In particular, the follo
wing three long-standing conjectures concern the size of a largest induced forest in a planar graph, and we conjecture that each of these can be generalized to the setting of fractional vertex-arboricity. In 1979, Albertson and Berman conjectured that every planar graph has an induced forest on at least half of its vertices, in 1987, Akiyama and Watanabe conjectured that every bipartite planar graph has an induced forest on at least five-eighths of its vertices, and in 2010, Kowalik, Luv{z}ar, and v{S}krekovski conjectured that every planar graph of girth at least five has an induced forest on at least seven-tenths of its vertices. We make progress toward the fractional generalization of the latter of these, by proving that every planar graph of girth at least five has fractional vertex-arboricity at most $2 - 1/324$.
A subgraph $H$ of an edge-coloured graph is called rainbow if all of the edges of $H$ have different colours. In 1989, Andersen conjectured that every proper edge-colouring of $K_{n}$ admits a rainbow path of length $n-2$. We show that almost all opt
imal edge-colourings of $K_{n}$ admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersens Conjecture holds for almost all optimal edge-colourings of $K_{n}$ and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
