Title of article :
Triangle-free graphs whose independence number equals the degree
Author/Authors :
Brandt، نويسنده , , Stephan، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2010
Pages :
8
From page :
662
To page :
669
Abstract :
In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class S of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph G must be regular of degree d = α ( G ) and the fractional chromatic number must satisfy χ f ( G ) = | G | / α ( G ) . We indicate that S is a rich family of graphs by determining the rational numbers c for which there is a graph G ∈ S with χ f ( G ) = c except for a small gap, where we cannot prove the full statement. The statements for c ≥ 3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c < 3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in S like chromatic number and toughness.
Keywords :
fractional chromatic number , Toughness , Triangle-free graph , independence number
Journal title :
Discrete Mathematics
Serial Year :
2010
Journal title :
Discrete Mathematics
Record number :
1599281
Link To Document :
بازگشت