Alon–Tarsi conjecture

E621147

The Alon–Tarsi conjecture is a prominent open problem in combinatorics and graph theory concerning orientations and colorings of graphs, with deep connections to Latin squares and polynomial method techniques.

All labels observed (2)

How this entity was disambiguated

Statements (44)

Predicate Object
instanceOf mathematical conjecture ⓘ
open problem in combinatorics ⓘ
conjecturedBy Michael Tarsi ⓘ
Noga Alon ⓘ
describedIn paper by Noga Alon and Michael Tarsi on colorings and orientations of graphs ⓘ
field combinatorics ⓘ
graph theory ⓘ
hasConnectionTo Latin squares ⓘ
Tutte polynomial ⓘ
acyclic orientations ⓘ
algebraic proof techniques in graph coloring ⓘ
bipartite Eulerian orientations ⓘ
coloring polynomial ⓘ
combinatorial Nullstellensatz ⓘ
difference between numbers of even and odd Latin squares ⓘ
even and odd orientations of graphs ⓘ
graph choosability ⓘ
graph polynomials ⓘ
list coloring of graphs ⓘ
orientation counting in graphs ⓘ
parity arguments in combinatorics ⓘ
parity of Latin squares ⓘ
polynomial method ⓘ
sign of permutations in Latin squares ⓘ
hasInfluenceOn development of algebraic methods in combinatorics ⓘ
research on graph colorings via orientations ⓘ
hasVariant Alon–Tarsi conjecture for Latin squares ⓘ
implies results on list colorings of planar graphs ⓘ
mainSubject graph colorings ⓘ
graph orientations ⓘ
namedAfter Michael Tarsi ⓘ
Noga Alon ⓘ
relatedConjecture circular choosability conjecture ⓘ
list coloring conjecture ⓘ
relatesTo Eulerian subgraphs ⓘ
bipartite graphs ⓘ
chromatic number of graphs ⓘ
complete bipartite graphs ⓘ
list chromatic number ⓘ
status open ⓘ
studiedIn algebraic graph theory ⓘ
extremal combinatorics ⓘ
usedIn applications of the combinatorial Nullstellensatz ⓘ
yearProposed 1992 ⓘ

How these facts were elicited

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Noga Alon → notableWork → Alon–Tarsi conjecture ⓘ
Combinatorial Nullstellensatz → relatedTo → Alon–Tarsi conjecture ⓘ
Alon–Tarsi conjecture → hasVariant → Alon–Tarsi conjecture for Latin squares ⓘ
linked to: Alon–Tarsi conjecture