rom $G$ by removing these triangles. Then we construct an auxiliary graph $G'$ with these triangles as vertices by connecting two of them with an edge if there is an edge in $G$ between the triangles. The graph $G'$ has maximum degree at most $3$, so it can be greedily $4$-colored. If we construct $G$ by adding back the triangles to $G_0$, in the order determined by their colors, then the procedure will end in polynomial time. $\Box$

P. Alimonti and V. Kann: Some APX-completeness results for cubic graphs, [*Theoret. Comput. Science*]{} [**237**]{} (2000), 123–134.

E. Asplund and B. Grünbaum: On a colouring problem, [*Math. Scand.*]{} [**8**]{} (1960), 181–188.

C. Berge: Färbung von Graphen, deren sämtlich bzw. deren ungerade Kreise starr sind. Beiträge zur Graphentheorie (Vorträge während des graphentheoretischen Kolloquiums in Halle im März 1960, German), [*Wiss. Zeitchr. Univ. Halle*]{} [**10**]{} (1961), 114.

B. Bollobás: [*Modern Graph Theory. Graduate Texts in Mathematics*]{} [**184**]{}, Springer-Verlag, New York, 1998.

J. P. Burling: [*On coloring problems of families of prototypes*]{} (PhD thesis), University of Colorado, Boulder, 1965.

S. Cabello, J. Cardinal, and S. Langerman: The clique problem in ray intersection graphs, [*Discrete Comput. Geom.*]{} [**50**]{}(3) (2013), 771–783.

J. Cardinal, M. S. Payne, and N. Solomon: Ramsey-type theorems for lines in 3-space, [*Discrete Mathematics & Theoretical Computer Science*]{} [**18**]{}(3) (2016), \#[14]{}. M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas: The strong perfect graph theorem, [*Ann. Math.*]{} [**164**]{}(1) (2006), 51–229.

R. P. Dilworth: A decomposition theorem for partially ordered sets, [*Ann. Math.*]{} [**51**]{}(1) (1950), 161–166.

G. A. Dirac: On rigid circuit graphs, [*Abh. Math. Sem. Univ. Hamburg*]{} [**25**]{} (1961), 71–76.

G. Ehrlich, S. Even, and R. E. Tarjan: Intersection graphs of curves in the plane, [*J. Combinatorial Theory Ser. B*]{} [**21**]{}(1) (1976), 8–20.