Coloration d'aretes a distance

Hervé Hocquard

Description

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

Sujets

• Première
• Coloration des arêtes d'un graphe
• Graph theory

Informations

• Publié par: davaj
• Date de parution: 01 mars 2012
• Nombre de lectures: 27
• Langue: Français

Extrait

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