Clique colourings of geometric graphs

Colin McDiarmid¹ ; Dieter Mitsche² ; Pawel Prałat³

¹Oxford University
²Université Jean Monnet
³Ryerson University

The electronic journal of combinatorics, Tome 25 (2018) no. 4

Résumé

A clique colouring of a graph is a colouring of the vertices such that no maximal clique is monochromatic (ignoring isolated vertices). The least number of colours in such a colouring is the clique chromatic number. Given $n$ points $\mathbf{x}_1, \ldots,\mathbf{x}_n$ in the plane, and a threshold $r>0$, the corresponding geometric graph has vertex set $\{v_1,\ldots,v_n\}$, and distinct $v_i$ and $v_j$ are adjacent when the Euclidean distance between $\mathbf{x}_i$ and $\mathbf{x}_j$ is at most $r$. We investigate the clique chromatic number of such graphs.We first show that the clique chromatic number is at most 9 for any geometric graph in the plane, and briefly consider geometric graphs in higher dimensions. Then we study the asymptotic behaviour of the clique chromatic number for the random geometric graph $\mathcal{G}$ in the plane, where $n$ random points are independently and uniformly distributed in a suitable square. We see that as $r$ increases from 0, with high probability the clique chromatic number is 1 for very small $r$, then 2 for small $r$, then at least 3 for larger $r$, and finally drops back to 2.

Détail

DOI : 10.37236/7159

Classification : 05C15, 05C35, 05C62, 05C69, 05C80, 60D05
Mots-clés : geometric graphs, random geometric graphs, clique chromatic number