THE FRACTIONAL CHROMATIC NUMBER OF MYCIELSKIS GRAPHS

Authors
LARSEN M PROPP J ULLMAN D
Citation
M. Larsen et al., THE FRACTIONAL CHROMATIC NUMBER OF MYCIELSKIS GRAPHS, Journal of graph theory, 19(3), 1995, pp. 411-416
Citations number
14
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Journal of graph theory → ACNP
ISSN journal
03649024
Volume
19
Issue
3
Year of publication
1995
Pages
411 - 416
Database
ISI
SICI code
0364-9024(1995)19:3<411:TFCNOM>2.0.ZU;2-E
Abstract
The most familiar construction of graphs whose clique number is much s maller than their chromatic number is due to Mycielski, who constructe d a sequence G(n) of triangle-free graphs with chi(G(n)) = n. In this article, we calculate the fractional chromatic number of G, and show t hat this sequence of numbers satisfies the unexpected recurrence a(n+1 ) = a(n) + (1/a(n)). (C) 1995 John Wiley & Sons, Inc.