5,016 problems

In combinatorial mathematics, Toida's conjecture, due to Shunichi Toida in 1977, is a refinement of the disproven Ádám's conjecture from 1967.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiho…

In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a w…

In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instruct…

In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that ca…

In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formul…

Read's conjecture is a conjecture, first made by Ronald Read, about the unimodality of the coefficients of chromatic polynomials in the context of graph theory. In 1974, S. G. Hogg…

In graph theory, the Graham–Pollak theorem states that the edges of an $n$ -vertex complete graph cannot be partitioned into fewer than $n-1$ complete bipartite graphs. It was firs…

Alspach's conjecture is a mathematical theorem that characterizes the disjoint cycle covers of complete graphs with prescribed cycle lengths. It is named after Brian Alspach, who p…

In graph theory, the Goldberg–Seymour conjecture states that, for a multigraph $G$…

In graph theory, the Kelmans–Seymour conjecture states that every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5. It is named…

In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conject…

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary…

The Kahn–Kalai conjecture, also known as the expectation threshold conjecture or more recently the Park-Pham Theorem, was a conjecture in the field of graph theory and statistical…

In combinatorial optimization, the Dinitz–Garg–Goemans conjecture, also called Goemans' conjecture or the cost conjecture, is a statement about single-source unsplittable flows. It…

In the mathematics of directed graphs, Woodall's conjecture is an unproven relationship between dicuts and dijoins. It was posed by Douglas Woodall in 1976.

Sidorenko's conjecture is a major conjecture in the field of extremal graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture states that for any bipar…

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 s…

In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.

In the study of graph algorithms, an implicit graph representation is a graph whose vertices or edges are not represented as explicit objects in a computer's memory, but rather are…

The imbalance conjecture is an open problem in graph theory concerning whether edge imbalance sequences are graphic, first formally stated by Kozerenko and Skochko in 2014.

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 comp…

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions…

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 (196…

Tuza's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning triangles in undirected graphs.