Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423434 | Discrete Mathematics | 2012 | 7 Pages |
Abstract
An inflation of a graph G is obtained by replacing vertices in G by disjoint cliques and adding all possible edges between any pair of cliques corresponding to adjacent vertices in G. We prove that the chromatic number of an arbitrary inflation F of the Petersen graph is equal to the chromatic number of some inflated 5-cycle contained in F. As a corollary, we find that Hadwiger's Conjecture holds for any inflation of the Petersen graph. This solves a problem posed by Bjarne Toft.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Anders Sune Pedersen,