Erdős–Gyárfás conjecture
In graph theory, the unproven Erdős–Gyárfás conjecture, made in 1995 by the prolific mathematician Paul Erdős and his collaborator András Gyárfás, states that every graph with minimum degree 3 contain
Lovász conjecture
In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says: Every finite connected vertex-transitive graph contains a Hamiltonian path. Originally Lás
Szymanski's conjecture
In mathematics, Szymanski's conjecture, named after Ted H. Szymanski, states that every permutation on the n-dimensional doubly directed hypercube graph can be routed with edge-disjoint paths. That is
Oberwolfach problem
The Oberwolfach problem is an unsolved problem in mathematics that may be formulated either as a problem of scheduling seating assignments for diners,or more abstractly as a problem in graph theory, o
Erdős–Faber–Lovász conjecture
In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says: If k complete graphs,
Turán's brick factory problem
Unsolved problem in mathematics: Can any complete bipartite graph be drawn with fewer crossings than the number given by Zarankiewicz? (more unsolved problems in mathematics) In the mathematics of gra
Vizing's conjecture
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing, and states that, if γ(G
Barnette's conjecture
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after , a professor emeritus at the University of California
Zarankiewicz problem
The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgr
Cycle double cover
In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph
Unfriendly partition
In the mathematics of infinite graphs, an unfriendly partition or majority coloring is a partition of the vertices of the graph into disjoint subsets, so that every vertex has at least as many neighbo
Sumner's conjecture
Sumner's conjecture (also called Sumner's universal tournament conjecture) states that every orientation of every -vertex tree is a subgraph of every -vertex tournament. David Sumner, a graph theorist
Hadwiger–Nelson problem
In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distan
Albertson conjecture
In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor
Erdős on Graphs
Erdős on Graphs: His Legacy of Unsolved Problems is a book on unsolved problems in mathematics collected by Paul Erdős in the area of graph theory. It was written by Fan Chung and Ronald Graham, based
Conway's 99-graph problem
In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor
Gyárfás–Sumner conjecture
In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree and complete graph , the graphs with neither nor as induced subgraphs can be properly colored using only a constant number o
Hadwiger conjecture (graph theory)
In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-c
GNRS conjecture
In theoretical computer science and metric geometry, the GNRS conjecture connects the theory of graph minors, the stretch factor of embeddings, and the approximation ratio of multi-commodity flow prob
Reconstruction conjecture
Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.
Babai's problem
In algebraic graph theory, Babai's problem was proposed in 1979 by László Babai.
Brouwer's conjecture
In the mathematical field of spectral graph theory, Brouwer's conjecture is a conjecture by Andries Brouwer on upper bounds for the intermediate sums of the eigenvalues of the Laplacian of a graph in
Erdős–Hajnal conjecture
In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is n
New digraph reconstruction conjecture
The reconstruction conjecture of Stanisław Ulam is one of the best-known open problems in graph theory. Using the terminology of Frank Harary it can be stated as follows: If G and H are two graphs on
Harborth's conjecture
In mathematics, Harborth's conjecture states that every planar graph has a planar drawing in which every edge is a straight segment of integer length. This conjecture is named after Heiko Harborth, an
Second neighborhood problem
In mathematics, the second neighborhood problem is an unsolved problem about oriented graphs posed by Paul Seymour. Intuitively, it suggests that in a social network described by such a graph, someone