# Erdos, Paul

## Multicolour Erdős--Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed and fixed colouring of with colours, there exists such that every colouring of the edges of contains either vertices whose edges are coloured according to or vertices whose edges are coloured with at most colours.

Keywords: ramsey theory

## Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

Problem   Bound the extremal number of in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

## Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

Conjecture   If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .

Keywords: chromatic number

## Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

Conjecture   If is a simple triangle-free graph, then there is a set of at most edges whose deletion destroys every odd cycle.

Keywords:

## Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.

Conjecture   For every finite family of graphs there exists an such that .

Keywords:

## Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index is the minimum number of colours in a strong edge-colouring of .

Conjecture  Keywords:

## Erdős–Straus conjecture ★★

Author(s): Erdos; Straus

Conjecture

For all , there exist positive integers , , such that .

Keywords: Egyptian fraction

## Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture is the only -chromatic double-critical graph

Keywords: coloring; complete graph

## Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of points in the plane in general position contains a subset of points which form a convex -gon.

## Middle levels problem ★★

Author(s): Erdos

Conjecture   Let be the bipartite graph whose vertices are the -subsets and the -subsets of a -element set, and with inclusion as the adjacency relationship. Then is Hamiltonian.

Keywords: 