The maximal clique and colourability of curve contact graphs (Q1382253)

A finite set \({\mathcal R}\) of curves (resp. straight line segments) in the plane is called a curve (resp. line segment) contact representation of a graph \(H\) if the interiors of any two curves (resp. line segments) of \({\mathcal R}\) are disjoint and \(H\) is the intersection graph of \({\mathcal R}\). The graph \(H\) is called the contact graph of \({\mathcal R}\) and is denoted by \(G ({\mathcal R})\). This paper proves that each complete graph \(K_n\) has a curve and a line segment contact representation \({\mathcal R}\) in which each contact point of \({\mathcal R}\) has degree at most \(k\), where \(k\) is a function of \(n\). This paper also establishes a polynomial algorithm for finding a maximal clique in \(H=G ({\mathcal R})\) and points out that the problems of finding the chromatic number and the independence number of \(G({\mathcal R})\) are in general NP-complete. Some open problems are raised at the end of this paper.