TOPICS
Search

Shift Graph

The shift graph SG_n is the graph whose vertices are the 2-element subsets of {1,2,...,n}, with a graph edge between {i,j} and {j,k} for every i<j<k (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 (n; 2) vertices and (n; 3) edges. It is a triangle-free graph, and for n>=2 its chromatic number is [log_2n], where [x] 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, SG_3 consists of the graph path joining {1,2} to {2,3} and the isolated vertex {1,3}. The graph vertex {1,n} is isolated for every n>=2.

For r>=2, SG_(2^r+1) contains exactly one vertex-induced subgraph that is (r+1)-vertex-critical. To describe it, put

I_l={2^l,2^l+1,...,2^r-2^(r-l)+2} for 0<=l<=r.

Its vertex set consists of the pairs {x,y} contained in at least one I_l (Kaiser et al. 2026, p. 2).

See also

Chromatic Number, Triangle-Free Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory. Berlin, Germany: Springer-Verlag, p. 372, 2008.Erdős, P. and Hajnal, A. "On Chromatic Number of Infinite Graphs." In Theory of Graphs (Proc. Colloq., Tihany, 1966) (Ed. P. Erdős and G. Katona). New York: Academic Press, pp. 83-98, 1968. https://www.renyi.hu/~p_erdos/1968-04.pdf.House of Graphs. Shift Graphs. P_2 + K_1.Kaiser, T.; Stehlík, M.; Škrekovski, R.; and Toft, B. "A Note on Vertex-Critical Induced Subgraphs of Shift Graphs." Elec. J. Combin. 33, P4.13, 2026. https://doi.org/10.37236/15178.

Cite this as:

Weisstein, Eric W. "Shift Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ShiftGraph.html

Subject classifications