International Journal of Mathematics and Mathematical Sciences
Volume 6 (1983), Issue 2, Pages 279-283

On the structure of a triangle-free infinite-chromatic graph of Gyarfas

Larry Eggan1,2 and Frank Harary3,4

1Mathematical Reviews, Ann Arbor 48109, MI, USA
2Illinois State University, Normal 61761, IL, USA
3Churchill College, Cambridge CV3 ODS, United Kingdom
4University of Michigan, Ann Arbor 48109, MI, USA

Received 22 June 1981; Revised 13 September 1982

Copyright © 1983 Larry Eggan and Frank Harary. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Gyárfás has recently constructed an elegant new example of a triangle-free infinite graph G with infinite chromatic number. We analyze its structure by studying the properties of a nested family of subgraphs Gn whose union is G.