Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649518 | Discrete Mathematics | 2010 | 8 Pages |
In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class SS of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph GG must be regular of degree d=α(G)d=α(G) and the fractional chromatic number must satisfy χf(G)=|G|/α(G)χf(G)=|G|/α(G). We indicate that SS is a rich family of graphs by determining the rational numbers cc for which there is a graph G∈SG∈S with χf(G)=cχf(G)=c except for a small gap, where we cannot prove the full statement. The statements for c≥3c≥3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c<3c<3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in SS like chromatic number and toughness.