Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2019: Graph Coloring

G
Topic
First Poster
Last Poster
Equivalence of EFL Conjecture and curve EFL conjecture
notethanol   1
N Dec 9, 2019 by JGeneson
EFL conjecture: Let $G$ be a graph consisting of $m$ copies of $K_m$, every pair of which has at most one vertex in common. Then, $\chi(G) = m$.

Curve EFL conjecture: Let $M$ be a set of $m$ curves such that every pair has at most one point in common. Then, $M$ has an EFL coloring with $m$ colors.

EFL conjecture $\implies$ Curve EFL conjecture

Within any given set of curves, imaginary points can be added to each curve so that Graph $G$ is composed of $m$
$K_m$'s while also ensuring that each $K_m$ has a maximum of one intersection. Thus, the EFL conjecture implies the Curve EFL conjecture.

Curve EFL conjecture $\implies$ EFL conjecture

Within any graph $G$, m curves (1, . . . , m) can be added so that each $K_i$'s intersections are intersections of the curves as well. Thus, the Curve EFL conjecture implies the EFL conjecture.

Since the two conjectures imply each other, they are equivalent.
1 reply
notethanol
Dec 1, 2019
JGeneson
Dec 9, 2019
No more topics!
a