THE FRACTIONAL CHROMATIC NUMBER OF MYCIELSKIS GRAPHS

被引：63

作者：

LARSEN, M

PROPP, J

ULLMAN, D

机构：

[1] MIT,CAMBRIDGE,MA 02139

[2] GEORGE WASHINGTON UNIV,WASHINGTON,DC

来源：

JOURNAL OF GRAPH THEORY | 1995年 / 19卷 / 03期

关键词：

D O I：

10.1002/jgt.3190190313

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The most familiar construction of graphs whose clique number is much smaller than their chromatic number is due to Mycielski, who constructed 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 that this sequence of numbers satisfies the unexpected recurrence a(n+1) = a(n) + (1/a(n)). (C) 1995 John Wiley & Sons, Inc.

引用

页码：411 / 416

页数：6