The Erdos-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on$n$vertices is at most n. Erdös considered this to be one of his three most favorite combinatorial problems and offered a $500 reward for a proof of this conjecture. We prove this conjecture for every large n. Here, we also provide a randomised algorithm to find such a colouring in polynomial time with high probability.

In 2009, Bang-Jensen asked whether there exists a function $g(k)$ such that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + g(k)$ arcs. In this paper, we answer the question by showing that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + 750k^2\log_2(k+1)$ arcs, and there is a polynomial-time algorithm to find the spanning subgraph.

Hadwiger's conjecture asserts that if a simple graph $G$ has no $K_{t+1}$ minor, then its vertex set $V(G)$ can be partitioned into $t$ stable sets. This is still open, but we prove under the same hypothesis that $V(G)$ can be partitioned into $t$ sets $X_1,\ldots,X_t$, such that for $1\le i\le t$, the subgraph induced on $X_i$ has maximum degree at most a function of $t$. This is sharp, in that the conclusion becomes false if we ask for a partition into $t-1$ sets with the same property.