Coloration fractionnaire

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}}.}$

Summarize Timeline Fact Check

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}}}$.

Summarize Timeline Fact Check

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]}.