Premium
Circular chromatic numbers of some reduced Kneser graphs
Author(s) -
Lih KoWei,
Liu Daphne DerFen
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10052
Subject(s) - combinatorics , mathematics , chromatic scale , disjoint sets , vertex (graph theory) , graph , wheel graph , discrete mathematics , graph power , line graph
The vertex set of the reduced Kneser graph KG 2 ( m,2 ) consists of all pairs { a,b } such that a, b ε{1,2,…, m } and 2≤| a − b |≤ m −2. Two vertices are defined to be adjacent if they are disjoint. We prove that, if m ≥4 and m ≠5, then the circular chromatic number of KG 2 ( m ,2) is equal to m −2, its ordinary chromatic number. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 62–68, 2002