Erdos, Paul


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

Author(s): Erdos

\begin{problem} Bound the extremal number of $C_{10}$ in the hypercube. \end{problem}

Keywords: cycles; extremal combinatorics; hypercube

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

Author(s): Erdos; Faber; Lovasz

\begin{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$. \end{conjecture}

Keywords: chromatic number

Odd-cycle transversal in triangle-free graphs ★★

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

\begin{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. \end{conjecture}

Keywords:

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.

\begin{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}))$ .% Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords:

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$.

\begin{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.}$$ \end{conjecture}

Keywords:

Erdős–Straus conjecture ★★

Author(s): Erdos; Straus

\begin{conjecture} % Enter your conjecture in LaTeX For all $n > 2$, there exist positive integers $x$, $y$, $z$ such that $$1/x + 1/y + 1/z = 4/n$$. % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

Keywords: Egyptian fraction

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 \Def{chromatic number} by two.

\begin{conjecture} $K_n$ is the only $n$-chromatic double-critical graph \end{conjecture}

Keywords: coloring; complete graph

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

\begin{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. \end{conjecture}

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

Middle levels problem ★★

Author(s): Erdos

\begin{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. \end{conjecture}

Keywords:

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

\begin{problem} For every $n$, is there a (least) positive integer $f(n)$ so that whenever a tournament has its edges colored with $n$ colors, there exists a set $S$ of at most $f(n)$ vertices so that every vertex has a monochromatic path to some point in $S$? \end{problem}

Keywords: digraph; edge-coloring; tournament

Syndicate content