Dégénérescence (théorie des graphes)

En théorie des graphes, la dégénérescence est un paramètre associé à un graphe non orienté. Un graphe est k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k, et la dégénérescence d'un graphe est le plus petit k tel qu'il est k-dégénéré. On peut de façon équivalente définir le paramètre en utilisant un ordre sur les sommets, on trouve alors le terme nombre de marquage.

La dégénérescence est une mesure de la non-densité du graphe.

Deux définitions équivalentesModifier

 
Un graphe 2-dégénéré dans l'ordre.

Un graphe est dit k-dégénéré si tout sous-graphe contient un nœud de degré inférieur ou égal à k. De façon équivalente, un graphe est k-dégénéré s'il existe un ordre sur les sommets tel que, pour tout sommet, le nombre d'arêtes vers des sommets plus petits dans l'ordre est au plus k[1].

On appelle dégénérescence d'un graphe le plus petit entier tel que le graphe est dégénéré. Les termes nombre de marquage et coloring number sont parfois utilisés[1].

PropriétésModifier

La dégénérescence est une borne supérieure sur le nombre chromatique. La dégénérescence est liée à d'autres paramètres de graphe tels que l'arboricité et la largeur arborescente.

La conjecture d'Erdős-Burr dit que pour tout entier p, il existe une constante c telle que tout graphe p-dégénéré à n sommets ait son nombre de Ramsey majoré par c.n.

Aspects algorithmiquesModifier

Il est possible de calculer la dégénérescence en temps linéaire[2].

UtilisationsModifier

La dégénérescence apparaît naturellement dans les problèmes de coloration de graphes[1]. Le concept de k-core, qui est très proche, est un outil de l'analyse des réseaux sociaux[3].

HistoireModifier

La définition utilisant l'ordre date de 1966, et est due à Paul Erdős et András Hajnal[4]. L'autre est apparue quatre ans plus tard, dans un article de Lick et White[5],[1].

Notes et référencesModifier

  1. a b c et d Clément Charpentier, Jeux de coloration de graphes et problèmes de coloration (Thèse de doctorat), Université de Bordeaux (lire en ligne), « Colorations de graphes : Marquage et dégénérescence », p. 17.
  2. D. W. Matula et L.L. Beck, « Smallest-last ordering and clustering and graph coloring algorithms », Journal of the ACM, vol. 30, no 3,‎ , p. 417-427 (DOI 10.1145/2402.322385, Math Reviews 0709826).
  3. Christos Giatsidis, Graph Mining and Community evaluation with degeneracy (thèse de doctorat), Ecole polytechnique, Palaiseau, (lire en ligne).
  4. (en) P. Erdős et A. Hajnal, « On chromatic number of graphs and set-systems », Acta Math. Acad. Sci. Hungar., vol. 17,‎ , p. 61-99 (lire en ligne).
  5. Lowell W Beineke, « Characterizations of derived graphs », Journal of Combinatorial Theory, Elsevier, vol. 9, no 2,‎ , p. 129-135.