Computations of fractional chromatic numbers this week tell me that for Fullerene Graphs the value is $5/2$. I have computed $100$ of these or more. Is there any theorem that would say this? Any information on formulas for fractional chromatic numbers of families of graphs would be welcome. I am aware that the Kneser graphs $K(a,b)$ have fractional chromatic number $a/b$. For the definition of a Fullerene graph see this MathWorld link.
Fractional chromatic number of fullerenes
7
$\begingroup$
graph-theory
-
0Hello Dr. Wagon; I wanted to alert you that there is a proposal for [a new StackExchange site for *Mathematica* questions](http://area51.stackexchange.com/proposals/37304). I was hoping you could maybe add your support to this proposal. Thanks in advance! (I'll delete this message after you've read it.) – 2011-12-20
1 Answers
1
Any fullerene contains pentagons. Each of the 5 vertices on a pentagon touches 2 others. At most 2 vertices on any pentagon can share a colour since adjacent vertices have different colours. Therefore the chromatic number of a pentagon is 5/2.
If some of the vertices of a pentagon are coloured then, if for example a vertex is red and blue, the 2 opposite vertices must be coloured so that one is red and the other is blue. A fullerene can be coloured with 5/2 colours by first colouring a pentagon, then all the adjacent pentagons, then any adjacent to the adjacent pentagons... then any adjacent hexagons, then another pentagon and its adjacent pentagons, then adjacent hexagons etc.
-
0Checking over my database I found that 3 of the 100-200 fullerenes I examined did not have 5/2... So this is intriguing. If your proof, Angela, holds water, then there will be something funny about these 3 cases. I double-checked with others that my fractional chi is correct on these 3. Example: – 2011-12-09