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

Main Article Content

Peter Johnson
Alexis Krumpelman


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.

Article Details

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