Erdős-Faber-Lovász conjecture

Encyclopedia : E : ER : ERD : Erdős-Faber-Lovász conjecture

---

In graph theory, the Erdős-Faber-Lovász conjecture (1972) is a very deep problem about the coloring of graphs. It says:

The union of k copies of k-cliques intersecting in at most one vertex pairwise is k-chromatic.

Erdős originally offered US$50 for proving the conjecture in the affirmative, and later raised the reward to US$500. It is easy to show that the desired chromatic number is less than [1 + k \sqrt].

See also

• Erdős conjecture

References

• Erdős, Paul (1981). On the combinatorial problems I would most like to see solved. Combinatorica 1, 25–42.

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?