![](/files/happy5.png)
Erdos, Paul
Multicolour Erdős--Hajnal Conjecture ★★★
![$ k\geq2 $](/files/tex/bf9a9dbad620e3800b95f9120dc9a950b967bbfd.png)
![$ \chi $](/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png)
![$ E(K_k) $](/files/tex/552f009361444261d52e6cc961a905f4d26ad439.png)
![$ m $](/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png)
![$ \varepsilon>0 $](/files/tex/d572eb4a7102086da01f1eaefee455fa2bce9456.png)
![$ K_n $](/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ \chi $](/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png)
![$ n^\varepsilon $](/files/tex/7bf7473b27385145f7e4eb3c462a5f2a27198913.png)
![$ m-1 $](/files/tex/ac0b25768e50cc2e9a824d01affc6ab439d8382c.png)
Keywords: ramsey theory
Turán Problem for $10$-Cycles in the Hypercube ★★
Author(s): Erdos
![$ C_{10} $](/files/tex/11903dbe89daae659b28a8bead9b43cae2995c3d.png)
Keywords: cycles; extremal combinatorics; hypercube
Erdős–Faber–Lovász conjecture ★★★
Author(s): Erdos; Faber; Lovasz
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
Keywords: chromatic number
Odd-cycle transversal in triangle-free graphs ★★
Author(s): Erdos; Faudree; Pach; Spencer
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ n^2/25 $](/files/tex/0db5eaf8ff84c2da58a206455442346f6fa11c19.png)
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.
![$ {\cal F} $](/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png)
![$ F\in {\cal F} $](/files/tex/1b6109e0bcc06d36efed4d6b15e1ff4e529f533c.png)
![$ ex(n, F ) = O(ex(n, {\cal F})) $](/files/tex/05fdebcd6442863bb0866ecaf1c43a1a9eada77c.png)
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
.
![$$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$](/files/tex/a63811dfccf4e3128accc3daca7041ff5097e2a2.png)
![$$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$](/files/tex/987d7e1dcf43bb92750a5d1dffe79abc224035c2.png)
Keywords:
Erdős–Straus 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.
![$ K_n $](/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
Keywords: coloring; complete graph
Erdös-Szekeres conjecture ★★★
![$ 2^{n-2} + 1 $](/files/tex/78669eb6d8b95f5ad57efe25b8ed4f27b42cb6f6.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
Keywords: combinatorial geometry; Convex Polygons; ramsey theory
Middle levels problem ★★
Author(s): Erdos
![$ G_n $](/files/tex/2afa33262e4932cbabeb3b77fb22ca709e6577de.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ (n+1) $](/files/tex/87f1e5711f3404d32b523e469e27906999a4723e.png)
![$ (2n+1) $](/files/tex/16e6f15efc0bd3f090158cdc96f6608cb001e814.png)
![$ G_n $](/files/tex/2afa33262e4932cbabeb3b77fb22ca709e6577de.png)
Keywords:
![Syndicate content Syndicate content](/misc/feed.png)