Coloration d'aretes a distance

107

pages

Français

Documents scolaires

2012

Écrit par
Hervé Hocquard

Publié par
davaj

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

107

pages

Français

Ebook

2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

davaj

Date de parution

01 mars 2012

Nombre de lectures

Langue

Français

Niveau: Secondaire, Lycée, Première
Coloration d'aretes a distance 2 Herve Hocquard Pascal Ochem Andre Raspaud Petru Valicov Universite de Bordeaux, France LIRMM 1er Mars 2012 H.H,P.O,A.R,P.V (LaBRI) Coloration d'aretes a distance 2 LIRMM 2012 1 / 41

strong edge-coloring

petru valicov

rec¸oivent des couleurs differentes

indice chromatique

meme arete

graph theory

Voir

Publié par

davaj

Date de parution

01 mars 2012

Nombre de lectures

Langue

Français

Coloration d’ar^etes a distance 2
Herve Hocquard Pascal Ochem Andre Raspaud
Petru Valicov
Universite de Bordeaux, France
LIRMM
er1 Mars 2012
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 1 / 411 4
3
2 5
0L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 410L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
1 4
3
2 5
J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 410L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
4
3
2 5
J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
1
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 410L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
4
3
5
J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
1
2
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 410L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
4
5
J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
1
3
2
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 410L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
5
J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
1 4
3
2
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 410L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
1 4
3
2 5
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 41J.L. Fouquet et J.L. Jolivet.
Strong edge-coloring of cubic planar graphs.
Progress in Graph Theory, pages 247-264, 1984.
k-coloration forte d’ar^etes
Une k-coloration forte d’ar^etes d’un graphe G est une application
c : E (G )!f 1;:::; kg de telle sorte que deux ar^etes adjacentes ou
adjacentes a une m^eme ar^ete re coivent des couleurs di erentes.
0L’ indice chromatique fort de G , (G ), est le plus petit entier k tel que Gs
admet une k-coloration forte d’ar^etes.
1 4
3
2 5
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 2 / 410 (G ) 2 ( 1) + 1s
Algorithme glouton

Δ
Δ−1
u v
Δ−1 Δ−1
H.H,P.O,A.R,P.V (LaBRI) Coloration d’ar^etes a distance 2 LIRMM 2012 3 / 41