Article ID Journal Published Year Pages File Type
4649518 Discrete Mathematics 2010 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,