Contents Online

# Journal of Combinatorics

## Volume 2 (2011)

### Number 3

### Independence and chromatic densities of graphs

Pages: 397 – 411

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

#### Authors

#### 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