Journal of Combinatorics

Volume 2 (2011)

Number 3

Independence and chromatic densities of graphs

Pages: 397 – 411

DOI: https://dx.doi.org/10.4310/JOC.2011.v2.n3.a3

Authors

Anthony Bonato (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Jason I. Brown (Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, Canada)

Graeme Kemkes (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Pawel Pralat (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Abstract

We consider graph densities in countably infinite graphs. Theindependence density of a finite graph $G$ of order $n$ is itsproportion of independent sets to all subsets of vertices, while thechromatic density is its proportion of proper $n$-colourings to allmappings from vertices of $G$ to $\{1, 2, \ldots, n\}$. For bothdensities, we extend their definition to countable graphs via limits ofchains of finite graphs. We show that independence densities exist forall chains, and are unique regardless of which limiting chain is used.We prove that independence densities are always rational; in fact, weprove the stronger fact that the closure of the set of possible valuesis contained in the rationals. In contrast, we show that the infiniterandom graph contains chains realizing all real numbers in $[0,1]$ as achromatic density.

Keywords

infinite graph, independent sets, graph colouring, graph density, infinite random graph

Full Text (PDF format)

Published 29 March 2012