On the Babai and Upper Chromatic Numbers of Graphs of Diameter 2





Chromatic number, clique number


The Babai numbers and the upper chromatic number are parameters that can be assigned to any metric space. They can, therefore, be assigned to any connected simple graph. In this paper we make progress in the theory of the first Babai number and the upper chromatic number in the simple graph setting, with emphasis on graphs of diameter 2.

Author Biography

Alexis Krumpelman, Morehead State University

Department of Mathematics



Aaron Abrams, The kth upper chromatic number of the line, Discrete Mathematics 169 (1997), 157-192.

Aaron Abrams, Upper chromatic numbers: an update, Geombinatorics 10 (2000), 4-11.

Aaron Abrams and Peter Johnson, Yet another species of forbidden-distances chromatic number, Geombinatorics 10 (2001), 89-95.

A.F. Archer, On the upper chromatic numbers of the reals, Discrete Mathematics 214 (2000), no. 1-3, 65-75.

P. Frankl and R.M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357-368.

D. Greenwell and P.D. Johnson Jr., Forbidding prescribed distances for designated colors, Geombinatorics 2 (1992), no. 1, 13-16.

Aubrey D.N.J de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28 (2018), 18-31.

Peter Johnson, 4 = B1(Q3) = B1(Q4)!, Geombinatorics 17 (2008), 117-123.

Peter Johnson and Albert Lee, Two theorems concerning the Babai numbers, Geombinatorics 15 (2006), 177-182.

Peter Johnson, Andrew Schneider, and Michael Tiemeyer, B1(Q3) = 4, Geombinatorics 16 (2007), 356-362.

Arnfried Kemnitz and Massimiliano Morangio, Coloring the line, Ars Combin. 85 (2007), 183-192.




How to Cite

Johnson, P., & Krumpelman, A. (2021). On the Babai and Upper Chromatic Numbers of Graphs of Diameter 2. Tamkang Journal of Mathematics, 52(1), 113-123. https://doi.org/10.5556/j.tkjm.52.2021.3430