Metraipolis › archive › dc_9cdbedab98f6

Coloration forte — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Coloration_forte
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-05T06:58:53.622Z
SHA-256 of the archived text
6523e7103778dd624f6ca27f0bf3831f59bcfc7710ad62345b6cbbbe5873e93c
Stable URL of this page
https://metraipolis.com/documento/dc_9cdbedab98f6

How to cite

Coloration forte — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Coloration_forte (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_9cdbedab98f6 (Metraipolis archive dc_9cdbedab98f6, sha256 6523e7103778dd624f6ca27f0bf3831f59bcfc7710ad62345b6cbbbe5873e93c)
BibTeX
@misc{dc9cdbedab98f6,
  title = {Coloration forte — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Coloration_forte},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_9cdbedab98f6; sha256 6523e7103778dd624f6ca27f0bf3831f59bcfc7710ad62345b6cbbbe5873e93c},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Coloration_forte. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En théorie des graphes, une coloration forte est une coloration de graphe dans laquelle chaque couleur apparaît exactement une fois dans chaque partition, avec une partition des sommets en sous-ensembles (disjoints) de même taille. Lorsque l'ordre du graphe G n'est pas divisible par k, on ajoute des sommets isolés à G juste assez pour rendre l'ordre de ce nouveau graphe G' divisible par k. Dans ce cas, une forte coloration de G' moins les sommets isolés ajoutés précédemment est considérée comme une forte coloration de G. Un graphe est fortement k-colorable si, pour chaque partition des sommets en deux ensembles de taille k, il admet une coloration forte. L' indice chromatique fort sχ(G) d'un graphe G est le plus petit nombre k tel que G est fortement k-colorable. Un graphe est fortement k-chromatique s'il a pour indice chromatique fort k. Certaines propriétés de sx(G): sχ(G) > Δ(G). sχ(G) ≤ 3 Δ(G) - 1 (Haxell) Asymptotiquement, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). (Haxell) Ici Δ(G) est le degré maximal. La notion d'indice chromatique fort a été introduite indépendamment par Noga Alon (1988) et Michael Fellows (1990).

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Coloration forte» — https://fr.wikipedia.org/wiki/Coloration_forte
Wikidata Q7624545: «(proper) vertex coloring» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7624545
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Coloration_forte?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 228941578, consultata il 2026-11-05T06:53:35.008Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: dc0a0a1d481022efc91fa25d36ed7e42f0963ce753e9a0d1adbb0387884818a5