Attributes | Values |
---|
rdfs:label
| |
rdfs:comment
| - 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. 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): 1.
* sχ(G) > Δ(G). 2.
* sχ(G) ≤ 3 Δ(G) - 1 (Haxell) 3.
* Asymptotiquement, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). (Haxell) Ici Δ(G) est le degré maximal. (fr)
|
sameAs
| |
Wikipage page ID
| |
Wikipage revision ID
| |
dbo:wikiPageWikiLink
| |
Link from a Wikipage to an external page
| |
page length (characters) of wiki page
| |
dct:subject
| |
prop-fr:wikiPageUsesTemplate
| |
prov:wasDerivedFrom
| |
foaf:depiction
| |
prop-fr:année
| |
prop-fr:doi
| |
prop-fr:lienAuteur
| |
prop-fr:nom
| - Alon (fr)
- Fellows (fr)
- Haxell (fr)
|
prop-fr:numéro
| |
prop-fr:pages
| |
prop-fr:prénom
| - P.E. (fr)
- Noga (fr)
- Michael R. (fr)
|
prop-fr:périodique
| |
prop-fr:titre
| - On the strong chromatic number (fr)
- The linear arboricity of a graph (fr)
- The strong chromatic number (fr)
- Transversals of vertex partition in graphs (fr)
|
prop-fr:volume
| |
thumbnail
| |
foaf:isPrimaryTopicOf
| |
has abstract
| - 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): 1.
* sχ(G) > Δ(G). 2.
* sχ(G) ≤ 3 Δ(G) - 1 (Haxell) 3.
* 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). (fr)
|
is dbo:wikiPageWikiLink
of | |
is Wikipage redirect
of | |
is oa:hasTarget
of | |
is foaf:primaryTopic
of | |