Shift Graph

The shift graph is the graph whose vertices are the 2-element subsets of , with an graph edge between and for every (Bondy and Murty 2008, p. 372). Equivalently, writing the two elements of each subset in increasing order, two vertices are adjacent iff the second element of one equals the first element of the other.

The shift graph has vertices and edges. It is a triangle-free graph, and for its chromatic number is , where denotes the ceiling function (Erdős and Hajnal 1968; Bondy and Murty 2008, p. 372). Consequently, these are triangle-free graphs with arbitrarily large chromatic number.

For example, consists of the graph path joining to and the isolated vertex . The graph vertex is isolated for every .