Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650242 | Discrete Mathematics | 2008 | 7 Pages |
Abstract
A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs Mm(C2t+1)Mm(C2t+1) of an odd cycle, Kneser graphs KG(n,k)KG(n,k), and Schrijver graphs SG(n,k)SG(n,k) are not cover graphs when m⩾0,t⩾1m⩾0,t⩾1, k⩾1k⩾1, and n⩾2k+2n⩾2k+2. These results have consequences in circular chromatic number.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Ko-Wei Lih, Chen-Ying Lin, Li-Da Tong,