Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 7 down vote favorite
1

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.

share|improve this question
If you don't get an answer here, you might try MathOverflow (but be sure to mention at each site that you have posted to the other). – Gerry Myerson Dec 3 '11 at 8:50
Are all your fullerenes on 60 vertices? – Chris Godsil Dec 4 '11 at 16:29
The ones I checked are up to 50 vertices. I am told that perhaps things don't get interesting until they are much larger, so maybe there is nothing to this "conjecture" about 5/2. – stan wagon Dec 5 '11 at 1:07
Hello Dr. Wagon; I wanted to alert you that there is a proposal for a new StackExchange site for Mathematica questions. 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.) – J. M. Dec 20 '11 at 6:59

1 Answer

up vote 1 down vote

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.

share|improve this answer
Checking 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: – stan wagon Dec 9 '11 at 16:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.