Coloring an intersection graph of lines and a circle

Question

Given a finite set of lines in the plane with no three meeting at a common point, and a circle that contain all intersection points of the lines in its interior, form a graph G whose vertices are the intersections of the pair of lines and the intersections of the lines with the circle with two vertices adjacent if they appear consecutive on one of the lines or consecutive on the circle. Prove that χ(G) ≤ 3.

I was leaning towards the idea of greedy coloring. If we remove the circle then the plane in rotatable in such a way that no 2 points have the same $x$ coordinate, then it's possible to sort the vertices according to their $x-$ coordinate and each one has at most 2 earlier neighbors in the ordering, hence $G$ is 3- colorable. The circle introduces constraints that cannot be solved by rotating the plane since I could always have a vertex that has 3 earlier neighbors in that ordering so I don't see how to go on using greedy coloring. One other idea was list coloring, but I got stock there too. Any ideas?

Answer 1

First $3$-colour all intersection points of lines as you describe.

Each intersection point on the circle has only one already coloured neighbour. So each point, $v$, on the circle has one colour, $c'(v)$, which it cannot use.

Let two adjacent points $v,w$ on the circle have $c'(v)\ne c'(w)$ and then colour $v$ with $c(w)$. Then go round the circle away from $w$ successively colouring points since each has at most two 'prohibited' colours. This will still apply when we reach $w$.

That leaves just one case, when every $c'(v)$ is the same colour. However, there are an even number of intersection points on the circle so, in that case, all the points on the circle can be coloured alternately with the two 'non-prohibited' colours.