| Property |
Value |
| dbo: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)
- 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)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2994 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1988 (xsd:integer)
- 1990 (xsd:integer)
- 1992 (xsd:integer)
- 2004 (xsd:integer)
|
| prop-fr:doi
|
- 10.100200 (xsd:double)
- 10.100700 (xsd:double)
- 10.101700 (xsd:double)
- 10.113700 (xsd:double)
|
| prop-fr:lienAuteur
|
- Penny Haxell (fr)
- Penny Haxell (fr)
|
| prop-fr:nom
|
- Alon (fr)
- Fellows (fr)
- Haxell (fr)
- Alon (fr)
- Fellows (fr)
- Haxell (fr)
|
| prop-fr:numéro
|
- 2 (xsd:integer)
- 3 (xsd:integer)
|
| prop-fr:pages
|
- 1 (xsd:integer)
- 206 (xsd:integer)
- 311 (xsd:integer)
- 857 (xsd:integer)
|
| prop-fr:prénom
|
- P.E. (fr)
- Noga (fr)
- Michael R. (fr)
- 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)
- 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
|
- 3 (xsd:integer)
- 13 (xsd:integer)
- 62 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| 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)
- 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)
|
| rdfs:label
|
- Coloration forte (fr)
- Coloration forte (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
