# Erdos, Paul

## 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 ★★

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 ★★

**Conjecture**

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

Keywords: Egyptian fraction

## Double-critical graph conjecture ★★

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 ★★★

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

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

## 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:

## Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

**Problem**For every , is there a (least) positive integer so that whenever a tournament has its edges colored with colors, there exists a set of at most vertices so that every vertex has a monochromatic path to some point in ?

Keywords: digraph; edge-coloring; tournament