Coloration d'aretes a distance

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