Graphe de Petersen généralisé

G(n,k) est isomorphe à G(n,l) si et seulement si kl ≡ ±1 (mod n )[9].

La maille de G(n,k ) est égale au moins à 3 et au plus à 8, en particulier[10] :

${\displaystyle g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.}$

Voici un tableau avec les valeurs exactes des mailles :

Condition	Maille
${\displaystyle n=3k}$	3
${\displaystyle n=4k}$	4
${\displaystyle k=1}$
${\displaystyle n=5k}$	5
${\displaystyle n=5k/2}$
${\displaystyle k=2}$
${\displaystyle n=6k}$	6
${\displaystyle k=3}$
${\displaystyle n=2k+2}$
${\displaystyle n=7k}$	7
${\displaystyle n=7k/2}$
${\displaystyle n=7k/3}$
${\displaystyle k=4}$
${\displaystyle n=2k+3}$
${\displaystyle n=3k\pm 2}$
sinon	8

En tant que graphes réguliers, et selon le théorème de Brooks, le nombre chromatique d'un graphe de Petersen généralisé ne peut être supérieur à son degré . Les graphes de Petersen généralisés sont cubiques, leur nombre chromatique est donc 2 ou 3. Plus précisément, on a :

${\displaystyle \chi (G(n,k))={\begin{cases}2&{\text{si}}\ n\ {\text{est pair et}}\ k\ {\text{est impair}}\\3&{\text{si}}\ n\ {\text{est impair et}}\ k\ {\text{est pair}}\\\end{cases}}}$

Par exemple, le nombre chromatique de ${\displaystyle G(5,2)}$ est 3.

• 
  Une 3-coloration du graphe de Petersen ${\displaystyle G(5,2)}$
• 
  Une 2-coloration du graphe de Desargues ${\displaystyle G(10,3)}$
• 
  Une 3-coloration du graphe de Dürer ${\displaystyle G(6,2)}$

Le graphe de Petersen, qui est un snark, a un indice chromatique égal à 4. Tous les autres graphes de Petersen généralisés ont l'indice chromatique égal à 3[11].

Le graphe de Petersen généralisé G(9, 2) est l'un des rares graphes connus pour ne posséder qu'une seule 3-coloration des arêtes[12]

.

• 
  Une 4-coloration des arêtes du graphe de Petersen ${\displaystyle G(5,2)}$
• 
  Une 3-coloration des arêtes du graphe de Dürer ${\displaystyle G(6,2)}$
• 
  Une 3-coloration des arêtes du dodécaèdre ${\displaystyle G(10,2)}$
• 
  Une 3-coloration des arêtes du graphe de Desargues ${\displaystyle G(10,3)}$
• 
  Une 3-colorationdes arêtes du graphe de Nauru ${\displaystyle G(12,5)}$

Le graphe de Petersen lui-même est le seul graphe de Petersen généralisé qui n'est pas 3-arêtes coloriable[13].