Home » Author index

Erdos, Paul


Graph Theory » Extremal G.T.

Multicolour Erdős--Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed $ k\geq2 $ and fixed colouring $ \chi $ of $ E(K_k) $ with $ m $ colours, there exists $ \varepsilon>0 $ such that every colouring of the edges of $ K_n $ contains either $ k $ vertices whose edges are coloured according to $ \chi $ or $ n^\varepsilon $ vertices whose edges are coloured with at most $ m-1 $ colours.

Keywords: ramsey theory

Posted by Jon Noel
updated October 10th, 2019
add new comment
Combinatorics

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

Author(s): Erdos

Problem   Bound the extremal number of $ C_{10} $ in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

Posted by Jon Noel
updated September 20th, 2015
add new comment
Graph Theory » Coloring » Vertex coloring

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

Author(s): Erdos; Faber; Lovasz

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

Keywords: chromatic number

Posted by Jon Noel
updated August 22nd, 2013
add new comment
Graph Theory » Extremal G.T.

Odd-cycle transversal in triangle-free graphs ★★

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

Conjecture   If $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle.

Keywords:

Posted by fhavet
updated March 6th, 2013
add new comment
Graph Theory

Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family $ {\cal F} $ of graphs and an integer $ n $, the Turán number $ ex(n,{\cal F}) $ of $ {\cal F} $ is the largest integer $ m $ such that there exists a graph on $ n $ vertices with $ m $ edges which contains no member of $ {\cal F} $ as a subgraph.

Conjecture   For every finite family $ {\cal F} $ of graphs there exists an $ F\in {\cal F} $ such that $ ex(n, F ) = O(ex(n, {\cal F})) $ .

Keywords:

Posted by fhavet
updated March 5th, 2013
add new comment
Graph Theory » Coloring » Edge coloring

Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph $ G $ 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 $ s\chi'(G) $ is the minimum number of colours in a strong edge-colouring of $ G $.

Conjecture   $$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$ $$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$

Keywords:

Posted by fhavet
updated March 1st, 2013
add new comment
Number Theory

Erdős–Straus conjecture ★★

Author(s): Erdos; Straus

Conjecture  

For all $ n > 2 $, there exist positive integers $ x $, $ y $, $ z $ such that $$1/x + 1/y + 1/z = 4/n$$.

Keywords: Egyptian fraction

Posted by ACW
updated July 14th, 2014
4 comments
Graph Theory » Coloring » Vertex coloring

Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

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

Conjecture   $ K_n $ is the only $ n $-chromatic double-critical graph

Keywords: coloring; complete graph

Posted by DFR
updated November 30th, 2009
2 comments
Geometry

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of $ 2^{n-2} + 1 $ points in the plane in general position contains a subset of $ n $ points which form a convex $ n $-gon.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

Posted by mdevos
updated April 14th, 2009
1 comment
Graph Theory » Basic G.T. » Cycles

Middle levels problem ★★

Author(s): Erdos

Conjecture   Let $ G_n $ be the bipartite graph whose vertices are the $ n $-subsets and the $ (n+1) $-subsets of a $ (2n+1) $-element set, and with inclusion as the adjacency relationship. Then $ G_n $ is Hamiltonian.

Keywords:

Posted by tchow
updated September 25th, 2008
add new comment
Syndicate content