Coloring intersection points of
line segments
Sam Lowery
Department of Mathematics & Statistics
2022 Symposium for Student Research,
Scholarship, and Creative Activity

Graphs

Graphs
vertices
edges

Complete graphs

𝐾!

𝐾"

𝐾#

𝐾$

𝐾%

Coloring a graph
Coloring a graph means coloring its vertices
so that adjacent vertices get different colors

Coloring a graph
𝜒(𝐺): smallest possible number of colors
with which a graph 𝐺 can be colored

Coloring a graph
𝜒(𝐺): smallest possible number of colors
with which a graph 𝐺 can be colored

𝜒 𝐺 =3

Coloring a graph

𝜒(𝐾& ) = 𝑛

Set of line segments

Set of line segments
𝑀

Intersection points
𝑃(𝑀)

Intersection points
𝑤(𝑀): most intersection points in a segment

Intersection points
𝑤(𝑀) = 5

Corresponding graph
𝐺'

Coloring a set of segments
Coloring a set of segments means coloring the
intersection points so that no segment has
ffffffff
points with the
same color.

Coloring a set of segments
𝜒(𝑀): smallest possible number of colors with
which a set of segments 𝑀 can be colored

Coloring a set of segments
𝜒(𝑀): smallest possible number of colors with
which a set of segments 𝑀 can be colored

𝜒 𝑀 =5

Erdős-Faber-Lovász Conjecture
Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& ,
every pair of which has at most one vertex in
common. Then, 𝜒(𝐺) = 𝑛.

Erdős-Faber-Lovász Conjecture
Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& ,
every pair of which has at most one vertex in
common. Then, 𝜒(𝐺) = 𝑛.

Erdős-Faber-Lovász Conjecture
Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& ,
every pair of which has at most one vertex in
common. Then, 𝜒(𝐺) = 𝑛.

Erdős-Faber-Lovász Conjecture
Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& ,
every pair of which has at most one vertex in
common. Then, 𝜒(𝐺) = 𝑛.

Erdős-Faber-Lovász Conjecture
Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& ,
every pair of which has at most one vertex in
common. Then, 𝜒(𝐺) = 𝑛.
𝜒(𝐺) cannot be
less than 𝑛, since
at least 𝑛 colors
are needed for
each copy of 𝐾&

Erdős-Faber-Lovász Conjecture
Let 𝐺 be a graph consisting of 𝑛 copies of 𝐾& ,
every pair of which has at most one vertex in
common. Then, 𝜒(𝐺) = 𝑛.
[Kang et al. 2021] announced a proof for large
enough 𝑛

Erdős-Faber-Lovász Conjecture
Let 𝑀 be a set of 𝑚 curves, each pair of which has
at most one point in common. Then, 𝜒 𝑀 ≤ 𝑚.

Erdős-Faber-Lovász Conjecture
Let 𝑀 be a set of 𝑚 curves, each pair of which has
at most one point in common. Then, 𝜒 𝑀 ≤ 𝑚.

Erdős-Faber-Lovász Conjecture
Let 𝑀 be a set of 𝑚 curves, each pair of which has
at most one point in common. Then, 𝜒 𝑀 ≤ 𝑚.

Erdős-Faber-Lovász Conjecture
Let 𝑀 be a set of 𝑚 curves, each pair of which has
at most one point in common. Then, 𝜒 𝑀 ≤ 𝑚.
𝜒(𝑀) can be less
than 𝑚.

Coloring a set of segments
Let 𝑀 be a set of 𝑚 segments. What’s 𝜒(𝑀)?

Bounds

𝑤 𝑀 ≤ 𝜒 𝑀 ≤ |𝑀|

Bounds
Need 𝑤(𝑀) colors
for the segment with
𝑤(𝑀) intersections

Follows from proof
of EFL Conjecture

𝑤 𝑀 ≤ 𝜒 𝑀 ≤ |𝑀|

Bounds
Need 𝑤(𝑀) colors
for the segment with
𝑤(𝑀) intersections

Follows from proof
of EFL Conjecture

𝑤 𝑀 ≤ 𝜒 𝑀 ≤ |𝑀|

easy to compute

Complexity of 𝜒(𝑀)
Computing 𝜒(𝑀) is NP-Complete, even if 𝑀 is a
set of segments where no five segments
intersect in the same point.
Reduction using a special case of PLANAR GRAPH
COLORING

Bounds
Need 𝑤(𝑀) colors
for the segment with
𝑤(𝑀) intersections

Follows from proof
of EFL Conjecture

𝑤 𝑀 ≤ 𝜒 𝑀 ≤ |𝑀|

easy to compute

Bounds
Need 𝑤(𝑀) colors
for the segment with
𝑤(𝑀) intersections

Follows from proof
of EFL Conjecture

𝑤 𝑀 ≤ 𝜒 𝑀 ≤ |𝑀|

hard to compute
easy to compute

Questions
Experimentally, 𝜒 𝑀 usually seems to be a lot
closer to 𝑤 𝑀 than to |𝑀|.

Questions
Experimentally, 𝜒 𝑀 usually seems to be a lot
closer to 𝑤 𝑀 than to |𝑀|.
• When is 𝜒 𝑀 = 𝑤 𝑀 ?

Questions
Experimentally, 𝜒 𝑀 usually seems to be a lot
closer to 𝑤 𝑀 than to |𝑀|.
• When is 𝜒 𝑀 = 𝑤 𝑀 ?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 1?

Questions
Experimentally, 𝜒 𝑀 usually seems to be a lot
closer to 𝑤 𝑀 than to |𝑀|.
• When is 𝜒 𝑀 = 𝑤 𝑀 ?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 1?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 2?

Questions
Experimentally, 𝜒 𝑀 usually seems to be a lot
closer to 𝑤 𝑀 than to |𝑀|.
• When is 𝜒 𝑀 = 𝑤 𝑀 ?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 1?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 2?
• Can 𝜒 𝑀 ≥ 𝑤 𝑀 + 3?

Questions
Experimentally, 𝜒 𝑀 usually seems to be a lot
closer to 𝑤 𝑀 than to |𝑀|.
• When is 𝜒 𝑀 = 𝑤 𝑀 ?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 1?

Characterizations
are hard to derive

• When is 𝜒 𝑀 = 𝑤 𝑀 + 2?
• Can 𝜒 𝑀 ≥ 𝑤 𝑀 + 3?

Hard to find one

Questions
Experimentally, 𝜒 𝑀 usually seems to be a lot
closer to 𝑤 𝑀 than to |𝑀|.
• When is 𝜒 𝑀 = 𝑤 𝑀 ?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 1?
• When is 𝜒 𝑀 = 𝑤 𝑀 + 2?
• Can 𝜒 𝑀 ≥ 𝑤 𝑀 + 3?

What is 𝜒 𝑀 for
𝑀 with special
structure?
Easier to answer

Some characterizations
Odd # of sides

“circuit-free
“grid-like
arrangements” arrangements”

“bisected polygon
arrangements”

𝜒 𝑀 = 𝑤(𝑀) 𝜒 𝑀 = 𝑤(𝑀) 𝜒 𝑀 = 𝑤 𝑀 + 2

Some characterizations

“standard drawing of 𝐾&,& ”
𝜒 𝑀 =

𝑥, 𝑦 : 1 ≤ 𝑥, 𝑦 ≤ 𝑛, gcd 𝑥, 𝑦 = 1 + 2

Approach for

____ family

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula for arbitrary 𝑛

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula for arbitrary 𝑛

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient

Approach for

____ family

• Wrote program to generate instance of size 𝑛
• Computed optimal coloring for 𝑛 = 2,3, … , 10
• Looked up sequence of chromatic numbers in Online
Encyclopedia on Integer Sequences
• Noticed it almost matches one sequence
• Modified formula for that sequence to match exactly
• Analytically proved formula for arbitrary 𝑛

– Proof is based on showing that sets of intersections are
grouped at different y-coordinates, and points in these
levels get the same color, which is necessary and sufficient
Longest diagonal segments
intersect all others, so 𝑤(𝑀)
colors are necessary, and also
sufficient

Some characterizations
If 𝑀 is a segment cactus different from
then 𝜒 𝑀 ≤ |𝑀| − 1.

,

What about lines?
In a set 𝑀 of lines, every pair of non-parallel
lines intersect
𝑤 𝑀 ≤ 𝜒 𝑀 ≤ |𝑀| still holds

What about lines?
The following are equivalent:
• If 𝑀 is a set of 𝑚 lines drawn in the plane,
then 𝑀 has a coloring with 𝑚 colors.
• If 𝑀 is a set of 𝑚 segments drawn in the
plane, then 𝑀 has a coloring with 𝑚 colors.

What about lines?
The following are equivalent:
• If 𝑀 is a set of 𝑚 lines drawn in the plane,
then 𝑀 has a coloring with 𝑚 colors.
• If 𝑀 is a set of 𝑚 segments drawn in the
plane, then 𝑀 has a coloring with 𝑚 colors.
An analogous statement does not necessarily
hold for subfamilies of segments/lines

Approach for ____ family

Approach for ____ family
• Randomly noticed one small example
𝜒 𝑀 =𝑤 𝑀 +2

Approach for ____ family
• Randomly noticed one small example
𝜒 𝑀 =𝑤 𝑀 +2

• Noticed another that was similar to it
𝜒 𝑀 =𝑤 𝑀 +2

Approach for ____ family
• Randomly noticed one small example
𝜒 𝑀 =𝑤 𝑀 +2

• Noticed another that was similar to it
𝜒 𝑀 =𝑤 𝑀 +2

• Tried to extend the pattern
• Harder to verify large examples by hand

Approach for ____ family
•
•
•
•

Wrote integer program to help verification
Used program to check more examples
Saw 𝜒 𝑀 = 𝑤 𝑀 + 2 holds for all of them
Analytically proved formula
– Proof is based on converting the set of segments
to a graph, finding a coloring that always works,
and showing that no smaller coloring exists

Future work
• Find a set with 𝜒 𝑀 ≥ 𝑤 𝑀 + 3 or show
this can’t exist.
• Run more extensive computational
experiments

Future work
• Find a set with 𝜒 𝑀 ≥ 𝑤 𝑀 + 3 or show
this can’t exist.
• Run more extensive computational
experiments

Thank you