Equivalence of EFL Conjecture and curve EFL conjecture
notethanol1
NDec 9, 2019
by JGeneson
EFL conjecture: Let be a graph consisting of copies of , every pair of which has at most one vertex in common. Then, .
Curve EFL conjecture: Let be a set of curves such that every pair has at most one point in common. Then, has an EFL coloring with colors.
EFL conjecture Curve EFL conjecture
Within any given set of curves, imaginary points can be added to each curve so that Graph is composed of 's while also ensuring that each has a maximum of one intersection. Thus, the EFL conjecture implies the Curve EFL conjecture.
Curve EFL conjecture EFL conjecture
Within any graph , m curves (1, . . . , m) can be added so that each '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.
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.