
arXiv: 1701.02693
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.
Extremal problems in graph theory, 05C80, 05C15, 05C35, Graph representations (geometric and intersection representations, etc.), Random graphs (graph-theoretic aspects), clique chromatic number, random geometric graphs, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), geometric graphs, FOS: Mathematics, Mathematics - Combinatorics, Geometric probability and stochastic geometry, Combinatorics (math.CO)
Extremal problems in graph theory, 05C80, 05C15, 05C35, Graph representations (geometric and intersection representations, etc.), Random graphs (graph-theoretic aspects), clique chromatic number, random geometric graphs, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), geometric graphs, FOS: Mathematics, Mathematics - Combinatorics, Geometric probability and stochastic geometry, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
