Coloration fractionnaire

En haut : une 3:1-coloration du cycle à 5 sommets et une 6:2-coloration.
En bas : Une 5:2-coloration du même graphe.

On se donne un ensemble C de a couleurs ; une a:b-coloration d'un graphe G est l'affectation, à chaque sommet, d'un ensemble de b couleurs parmi les a couleurs de C de telle manière que les ensembles de couleurs de deux sommets adjacents sont disjoints. Si b=1, il s'agit d'une coloration au sens usuel du terme. Le b-nombre chromatique noté ${\displaystyle \chi _{b}(G)}$ est le plus petit a tel qu'une a:b-coloration existe. De mainière équivalente, elle peut être définie comme un homomorphisme sur le graphe de Kneser KG_a,b.

Le nombre chromatique fractionnaire est le nombre ${\displaystyle \chi _{f}(G)}$ défini par

${\displaystyle \chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}$

La limite existe parce que ${\displaystyle \chi _{b}(G)}$ est sous-additive, autrement dit ${\displaystyle \chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G)}$.

nombre chromatique fractionnaire

Le nombre chromatique fractionnaire peut être défini de manière équivalente en termes probabilistes : ${\displaystyle \chi _{f}(G)}$ est le plus petit k pour lequel il existe une distribution de probabilité sur les ensembles indépendants de G telle que pour chaque sommet v, et pour chaque ensemble indépendant S tiré de la distribution, on a :

${\displaystyle \Pr(v\in S)\geq {\frac {1}{k}}.}$

On a

${\displaystyle \chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}}\quad }$ et ${\displaystyle \quad \omega (G)\leq \chi _{f}(G)\leq \chi (G)}$,

où n(G) est le nombre de sommets du graphe, ${\displaystyle \alpha (G)}$ est la taille maximale d'un ensemble indépendant, ${\displaystyle \omega (G)}$ is the nombre de clique, et ${\displaystyle \chi (G)}$ est le nombre chromatique.

En outre, le nombre chromatique fractionnaire est proche du nombre chromatique à un facteur logarithmique près[1], en fait, on a :

${\displaystyle {\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G)}$.

Les graphes de Kneser sont des exemples où le rapport ${\displaystyle \chi (G)/\chi _{f}(G)}$ est arbitrairement grand, puisque ${\displaystyle \chi (KG_{m,n})=m-2n+2,}$ alors que ${\displaystyle \chi _{f}(KG_{m,n})={\tfrac {m}{n}}}$.

Le nombre chromatique fractionnaire ${\displaystyle \chi _{f}(G)}$ d'un graphe G peut être obtenu comme solution à un programme linéaire. Soit ${\displaystyle {\mathcal {I}}(G)}$ l'ensemble de tous les ensembles indépendants de G, et soit ${\displaystyle {\mathcal {I}}(G,x)}$ l'ensemble de tous les ensembles indépendants qui contiennent le sommet x. Pour chaque ensemble indépendant I, on définit une variable réelle non négative x_I. Alors ${\displaystyle \chi _{f}(G)}$ est la valeur minimale de

${\displaystyle \sum _{I\in {\mathcal {I}}(G)}x_{I},}$

soumis à

${\displaystyle \sum _{I\in {\mathcal {I}}(G,x)}x_{I}\geq 1}$

pour chaque sommet ${\displaystyle x}$.

Le programme dual de ce programme linéaire calcule le nombre de clique fractionnaire, une relaxation aux nombres rationnels de la notion de nombre de clique. C'est une pondération des sommets de G telle que le poids total attribué à tout ensemble indépendant est au plus 1. Le théorème de la dualité forte de la programmation linéaire garantit que les solutions optimales des deux programmes linéaires ont la même valeur. Cependant chaque programme linéaire peut avoir une taille exponentielle en fonction du nombre de sommets de G, et le calcul du nombre chromatique fractionnaire d'un graphe est NP-difficile[2]. Cela contraste avec le problème de coloration fractionnaire des arêtes d'un graphe, qui peut être résolu en temps polynomial. C'est une conséquence directe du théorème d'Edmonds des polytopes[3] - [4].

Les applications de la coloration fractionnaires de graphes comprennent la planification d'activités. Dans ce cas, le graphe G est un graphe de conflit ; en d'autres termes, une arête de G entre les nœuds u et v indique que u et v ne peuvent pas être actifs simultanément. Autrement dit, l'ensemble des nœuds qui sont actifs simultanément doit être un ensemble indépendant dans le graphe G.

Une coloration fractionnaire optimale du graphe G fournit alors un calendrier le plus court possible, de sorte que chaque nœud est actif pendant (au moins) 1 unité de temps au total, et qu'à tout moment, l'ensemble des nœuds actifs est un ensemble indépendant. Si on a une solution x au programme linéaire ci-dessus, on parcourt simplement tous les ensembles indépendants I dans un ordre arbitraire. Pour chaque I, les nœuds dans I sont actifs pour ${\displaystyle x_{I}}$ unités de temps ; pendant ce temps, chaque nœud qui n'est pas dans I est inactif.

Plus concrètement, chaque nœud de G peut représenter une transmission dans un réseau de communication sans fil ; les arêtes de G représentent les « interférences » entre les transmissions. Chaque transmission doit être active pendant une unité de temps au total ; une coloration fractionnaire optimale du graphe fournit un programme de longueur minimale (ou, de manière équivalente, un programme de largeur de bande maximale) qui est sans conflits.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Fractional coloring » (voir la liste des auteurs).

• Zdeněk Dvořák