Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1709452 | Applied Mathematics Letters | 2011 | 6 Pages |
Abstract
Zykov designed one of the oldest known families of triangle-free graphs with arbitrarily high chromatic number. We determine the fractional chromatic number of the Zykov product of a family of graphs. As a corollary, we deduce that the fractional chromatic numbers of the Zykov graphs satisfy the same recurrence relation as those of the Mycielski graphs, that is an+1=an+1an. This solves a conjecture of Jacobs.
Keywords
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Pierre Charbit, Jean Sébastien Sereni,