The fractional chromatic number of Zykov products of graphs
Copyright policy )The fractional chromatic number of Zykov products of graphs
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 a(n+1) = a(n) + 1/a(n). This solves a conjecture of Jacobs.
- Centre national de la recherche scientifique France
- Charles University Czech Republic
- Université Paris Cité France
- French National Centre for Scientific Research France
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Coloring of graphs and hypergraphs, triangle-free graphs, Applied Mathematics, Graph operations (line graphs, products, etc.), fractional coloring, Fractional coloring, Triangle-free graphs, Zykov graphs, Triangle-free graphs
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Coloring of graphs and hypergraphs, triangle-free graphs, Applied Mathematics, Graph operations (line graphs, products, etc.), fractional coloring, Fractional coloring, Triangle-free graphs, Zykov graphs, Triangle-free graphs
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!