As a follow-up to the problem of coloring triangle-free line segment intersection graphs that I posted the other day, here's another line segment intersection representation of the Grötzsch graph. This time I drew it with only four different slopes of line segments, making it obvious that it can be 4-colored (just use a different color for each slope). And conversely the fact that this graph requires four colors implies that I couldn't have drawn it with fewer than four slopes. Is there a bound on the number of distinct slopes needed to realize all triangle-free line segment intersection graphs? It seems likely to be hard to prove that this number is bounded, if it is, since that would also solve the coloring problem. But maybe it's easy to come up with a family of triangle-free line segment intersection graphs that require an unbounded number of slopes?

Line segment intersection representation of the Grötzsch graph

A natural candidate for an (infinite) line segment intersection graph requiring an unbounded number of slopes is the order-4 pentagonal tiling of the hyperbolic plane, the Klein model of which forms a triangle-free line segment arrangement in the Euclidean plane. But I don't see an easy way to get a handle on how many slopes it needs.





Comments:

passacaglio:
2009-10-28T07:03:52Z
Intuitively, it seems related to our problem with the complexity of the 3D straight skeleton, in a reverse way: we have the number of colors (i.e., number of original faces), and we wish to know what is the possible way to construct a maximal graph such that the patches have a limit in the number of mutual intersections (which is derived the structural properties of the skeleton).