Strong coloring
http://dbpedia.org/resource/Strong_coloring
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every part. A graph is strongly k-colorable if, for each partition of the vertices into sets of size k, it admits a strong coloring. When the order of the graph G is not divisible by k, we add isolated vertices to G just enough to make the order of the new graph G′ divisible by k. In that case, a strong coloring of G′ minus the previously added isolated vertices is considered a strong coloring of G.
rdf:langString
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.
rdf:langString
rdf:langString
Coloration forte
rdf:langString
Strong coloring
xsd:integer
690775
xsd:integer
1039488847
rdf:langString
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).
rdf:langString
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every part. A graph is strongly k-colorable if, for each partition of the vertices into sets of size k, it admits a strong coloring. When the order of the graph G is not divisible by k, we add isolated vertices to G just enough to make the order of the new graph G′ divisible by k. In that case, a strong coloring of G′ minus the previously added isolated vertices is considered a strong coloring of G. The strong chromatic number sχ(G) of a graph G is the least k such that G is strongly k-colorable.A graph is strongly k-chromatic if it has strong chromatic number k. Some properties of sχ(G): 1.
* sχ(G) > Δ(G). 2.
* sχ(G) ≤ 3 Δ(G) − 1. 3.
* Asymptotically, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). Here, Δ(G) is the maximum degree. Strong chromatic number was independently introduced by Alon (1988) and Fellows (1990).
xsd:nonNegativeInteger
4959
