Sumner's conjecture

Sumner's conjecture (also called Sumner's universal tournament conjecture) is a conjecture in extremal graph theory on oriented trees in tournaments.

[1] David Sumner, a graph theorist at the University of South Carolina, conjectured in 1971 that tournaments are universal graphs for polytrees.

The conjecture was proven for all large

by Daniela Kühn, Richard Mycroft, and Deryk Osthus.

, in which all edges are oriented outward from the central vertex to the leaves.

cannot be embedded in the tournament formed from the vertices of a regular

-gon by directing every edge clockwise around the polygon.

For, in this tournament, every vertex has indegree and outdegree equal to

[3] Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytrees.

, and the maximum outdegree is an integer greater than or equal to the average.

The following partial results on the conjecture have been proven.

Rosenfeld (1972) conjectured that every orientation of an

[7] After partial results by Thomason (1986), this was proven by Havet & Thomassé (2000a).

Havet and Thomassé[9] in turn conjectured a strengthening of Sumner's conjecture, that every tournament on

This has been confirmed for almost every tree by Mycroft and Naia (2018).

Burr (1980) conjectured that, whenever a graph

Because complete graphs require a different color for each vertex, Sumner's conjecture would follow immediately from Burr's conjecture.

[10] As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of