11
$\begingroup$

Given $n$ lines on the plane, consider all their intersection points. Find the minimal number $d=d(n)$ such that they may be always colored in $d$ colors so that on each line any two consecutive points have different color. Of course, $d(n)\leqslant 4$ as this graph is planar. But is it true that $d(n)=3$ for all $n\geqslant 3$?

There is an old olympiad problem that 3 colors are enough if no three lines are concurrent. I gave it to children forgetting this condition, and so now I wonder whether is this still true.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ An alternative construction to that given below is to draw a $K_5$ in the conventional fashion then delete two non-adjacent boundary pieces. The inner cycle has a unique $3$-colouring $12123$ up to isomorphism, and then the points of the star are coloured $33312$, with one of the pairs of $3$'s adjacent. This also uses $8$ lines, which makes me wonder if there's a construction that uses fewer. $\endgroup$
    – Ben Barber
    Commented Feb 15, 2017 at 19:54
  • $\begingroup$ Nice question. The original problem follows from Grötzsch's Theorem, but that is a bit like killing a mosquito with a cannon. $\endgroup$
    – Tony Huynh
    Commented Feb 16, 2017 at 13:02

1 Answer 1

Reset to default
12
$\begingroup$

No, here is an example that needs four colours (if I have understood the question correctly):

enter image description here

(there are other intersection points not shown, of course, but these are irrelevant)

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ (How I came up with this: I wanted to make an odd cycle, so chromatic number 3, and then a point in the middle connected to everyone to force it to be 4. This can't be done, so instead I gave up on one of the points. Then when I tried this with a 7 cycle I noticed an extra incidence at the top which does the same job). $\endgroup$
    – Thomas Bloom
    Commented Feb 15, 2017 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .