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
Equivalence of two conjectures
notethanol   3
N Dec 9, 2019 by JGeneson
In Brimkov proposition 17, we are given that Conjecture 3 is true if and only if Conjecture 4 is true.

(Note that Conjecture 3 is the Line EFL Conjecture (or Conjecture A in the exercise): "Let M be a set of m lines drawn in the plane. Then, M has an EFL coloring with m colors")
(Also note that Conjecture 4 is the Segment EFL Conjecture (or Conjecture B in the exercise): "Let M be a set of m segments drawn in the plane. Then, M has an EFL coloring with m colors")

Thus, if Conjecture 3 is true, then Conjecture 4 is also true; if Conjecture 3 is false, then Conjecture 4 is also false. Since the 2 conjectures have the same truth values, it can be said that Conjectures 3 and 4 are equivalent.
3 replies
notethanol
Oct 19, 2019
JGeneson
Dec 9, 2019
No more topics!
a