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
Problem 4: outline
notethanol   1
N Dec 16, 2019 by JGeneson
EFL segment conjecture: Let $M$ be a set of $m$ segments such that every pair has at most one point in common. Then, $M$ has an EFL coloring with $m$ colors.

The EFL segment conjecture is true in general: it can be applied to segments built on planar graphs.

Through a proof by Induction, the conjecture can be first proved for the base case. Then, by successively picking a segment that intersects a segment whose intersection points are already colored (starting with an arbitrary assignment of colors to intersection points of segments), an EFL coloring can be achieved--with all intersection points of $M$ colored.
1 reply
notethanol
Dec 14, 2019
JGeneson
Dec 16, 2019
No more topics!
a