Nombre chromatique et sous-graphes induits (Partie 1) PDF

NOUVEAUTÉS DE SOLIDWORKS® 2021— CAO 3D

la longueur de courbes et non la longueur cordale. Simplification et amélioration des assemblages. • Modèles simplifiés enregistrés en tant.

Nombre chromatique et sous-graphes induits (Partie 1)

8 juin 2020 Aucun cycle ? Forêt. Aucun cycle (induit) de longueur 4+ ? Graphe cordal. Marthe Bonamy. Nombre chromatique et sous-graphes induits.

Sur la coloration de certains graphes sans trou pair

16 nov. 2020 Un trou est un cycle de longueur ? 4. C4. C5. C6. C7. Définition. Un graphe est dit cordal s'il est sans trou. graphe non-cordal.

Longueur Arborescente des Graphes S´erie-Parall`eles†

La longueur d'une décomposition arborescente d'un graphe G est la plus grande 1 si et seulement si G est un graphe cordal (sans cycles induits de.

Géométrie hyperbolique

10 mars 2010 la longueur d'une courbe dans tout plan hyperbolique. En effet si A est un plan hyperbolique il existe une isométrie ? de A vers H2 unique ...

Théorie des graphes

17 mars 2012 Un graphe est cordal (ou triangulé) si tout cycle de longueur ? 4 possède une corde. G1 est cordal mais pas G2. Les graphes complets (Kn) ...

Graphes triangulés

6 avr. 2016 ... par les sommets d'un cycle de longueur 4 ou 5 contient un sommet adjacent `a tous les autres sommets du cycle. On dit aussi cordal.

Nombre chromatique et sous-graphes induits (Partie 2)

15 juin 2020 Un graphe est dit cordal si il ne contient pas de trou.a. aUn trou dans un graphe G est un cycle induit de G de longueur ? 4.

3 semaine du DE

occuper environ la moitié de la longueur de l'embryon. La ligne primitive résulte de la prolifération et (canal cordal – plaque cordale-corde dorsale) ...

STRUCTURE CORDALE de la micro-structure à la micro-fonction

structure cordale. • Epithélium (E). • Membrane basale structure cordale (2). Gray et al 2000 ... les plus étirables (jusqu'à 2 fois leur longueur).

Nombre chromatique et sous-graphes induits

(Partie 1)

Marthe Bonamy et Irena Penev

8 juin 2020

Marthe BonamyNombre chromatique et sous-graphes induits1/10

Graphes

Reseau de trains. Representer n'importe quelles contraintes.ParisRouen

MontpellierBordeauxLyon

Pas ici : ar^etes multiples, ar^etes ponderees, ar^etes dirigees. Marthe BonamyNombre chromatique et sous-graphes induits2/10

Graphes

Reseau de trains. Representer n'importe quelles contraintes.ParisRouen

MontpellierBordeauxLyon

Pas ici : ar^etes multiples, ar^etes ponderees, ar^etes dirigees. Marthe BonamyNombre chromatique et sous-graphes induits2/10

Graphes

Reseau de trains. Representer n'importe quelles contraintes.ParisRouen

MontpellierBordeauxLyon

Pas ici : ar^etes multiples, ar^etes ponderees, ar^etes dirigees. Marthe BonamyNombre chromatique et sous-graphes induits2/10

Graphes

Reseau de trains. Representer n'importe quelles contraintes.ParisRouen

MontpellierBordeauxLyon

Pas ici : ar^etes multiples, ar^etes ponderees, ar^etes dirigees. Marthe BonamyNombre chromatique et sous-graphes induits2/10

Graphes

Reseau de trains. Representer n'importe quelles contraintes.ParisRouen

MontpellierBordeauxLyon

Pas ici : ar^etes multiples, ar^etes ponderees, ar^etes dirigees. Marthe BonamyNombre chromatique et sous-graphes induits2/10

Graphes

Reseau de trains. Representer n'importe quelles contraintes.ParisRouen

MontpellierBordeauxLyon

Pas ici : ar^etes multiples, ar^etes ponderees, ar^etes dirigees. Marthe BonamyNombre chromatique et sous-graphes induits2/10

Graphes planaires

Question (Guthrie 1852)

Toutes les cartes sont-elles4-coloriables?Marthe BonamyNombre chromatique et sous-graphes induits3/10

Graphes planaires

Question (Guthrie 1852)

Toutes les cartes sont-elles4-coloriables?Marthe BonamyNombre chromatique et sous-graphes induits3/10

Graphes planaires

Question (Guthrie 1852)

Toutes les cartes sont-elles4-coloriables?Marthe BonamyNombre chromatique et sous-graphes induits3/10

Graphes planaires

Question (Guthrie 1852)

Toutes les cartes sont-elles4-coloriables?Marthe BonamyNombre chromatique et sous-graphes induits3/10

Graphes planaires

Question (Guthrie 1852)

Toutes les cartes sont-elles4-coloriables?Marthe BonamyNombre chromatique et sous-graphes induits3/10

Graphes planaires

Question (Guthrie 1852)

Toutes les cartes sont-elles4-coloriables?Marthe BonamyNombre chromatique et sous-graphes induits3/10

Coloration

1212
3

cd)c6=d: Nombre minimum de couleurs pour garantir :!: Taille maximale d'une clique: Taille maximale d'un stableg: Taille minimale d'un cycle!

jVj Marthe BonamyNombre chromatique et sous-graphes induits4/10

Coloration

1212
3

cd)c6=d: Nombre minimum de couleurs pour garantir :!: Taille maximale d'une clique: Taille maximale d'un stableg: Taille minimale d'un cycle!

jVj Marthe BonamyNombre chromatique et sous-graphes induits4/10

Coloration

1212
3

cd)c6=d: Nombre minimum de couleurs pour garantir :!: Taille maximale d'une clique: Taille maximale d'un stableg: Taille minimale d'un cycle!

jVj Marthe BonamyNombre chromatique et sous-graphes induits4/10

Quelques concepts de base

Clique :

Stable :

Cycle :

Marthe BonamyNombre chromatique et sous-graphes induits5/10

Coloration

1212
3

cd)c6=d: Nombre minimum de couleurs pour garantir :!: Taille maximale d'une clique: Taille maximale d'un stableg: Taille minimale d'un cycle!

jVj) jVj (1)Marthe BonamyNombre chromatique et sous-graphes induits6/10

Coloration

1212
3

cd)c6=d: Nombre minimum de couleurs pour garantir :!: Taille maximale d'une clique: Taille maximale d'un stableg: Taille minimale d'un cycle!

jVj) jVj (1)Marthe BonamyNombre chromatique et sous-graphes induits6/10

Coloration

1212
3

cd)c6=d: Nombre minimum de couleurs pour garantir :!: Taille maximale d'une clique: Taille maximale d'un stableg: Taille minimale d'un cycle!

jVj) jVj (1)Marthe BonamyNombre chromatique et sous-graphes induits6/10 +!?+!log2jVj(par induction) nombres de RamseyPeut-on obtenir!pjVj? (Parallele avec le theoreme de Dilworth)Non: p rendreun grand ensemble de sommets, et me ttre chaque ar^ete avec probabilite 0.5.Il existe une famille innie de graphes satisfaisant +!5log2jVj.Marthe BonamyNombre chromatique et sous-graphes induits7/10 +!?+!log2jVj(par induction) nombres de RamseyPeut-on obtenir!pjVj? (Parallele avec le theoreme de Dilworth)Non: p rendreun grand ensemble de sommets, et me ttre chaque ar^ete avec probabilite 0.5.Il existe une famille innie de graphes satisfaisant +!5log2jVj.Marthe BonamyNombre chromatique et sous-graphes induits7/10 +!?+!log2jVj(par induction) nombres de RamseyPeut-on obtenir!pjVj? (Parallele avec le theoreme de Dilworth)Non: p rendreun grand ensemble de sommets, et me ttre chaque ar^ete avec probabilite 0.5.Il existe une famille innie de graphes satisfaisant +!5log2jVj.Marthe BonamyNombre chromatique et sous-graphes induits7/10 +!?+!log2jVj(par induction) nombres de RamseyPeut-on obtenir!pjVj? (Parallele avec le theoreme de Dilworth)Non: p rendreun grand ensemble de sommets, et me ttre chaque ar^ete avec probabilite 0.5.Il existe une famille innie de graphes satisfaisant +!5log2jVj.Marthe BonamyNombre chromatique et sous-graphes induits7/10 Et si pas de grosse clique ?...pas de petit cycle ?

Theoreme (Mycielski 1955)

8k, il y a un grapheHkavec(Hk)ket!(Hk) = 2.Theoreme (Erd}os 1959)

8k,8`, il y a un grapheHkavec(Hk)k,!(Hk) = 2et

g(Hk) =`.Marthe BonamyNombre chromatique et sous-graphes induits8/10 Et si pas de grosse clique ?...pas de petit cycle ?

Theoreme (Mycielski 1955)

8k, il y a un grapheHkavec(Hk)ket!(Hk) = 2.Theoreme (Erd}os 1959)

8k,8`, il y a un grapheHkavec(Hk)k,!(Hk) = 2et

g(Hk) =`.Marthe BonamyNombre chromatique et sous-graphes induits8/10 Et si pas de grosse clique ?...pas de petit cycle ?

Theoreme (Mycielski 1955)

8k, il y a un grapheHkavec(Hk)ket!(Hk) = 2.Theoreme (Erd}os 1959)

8k,8`, il y a un grapheHkavec(Hk)k,!(Hk) = 2et

g(Hk) =`.Marthe BonamyNombre chromatique et sous-graphes induits8/10 Et si pas de grosse clique ?...pas de petit cycle ?

Theoreme (Mycielski 1955)

8k, il y a un grapheHkavec(Hk)ket!(Hk) = 2.Theoreme (Erd}os 1959)

8k,8`, il y a un grapheHkavec(Hk)k,!(Hk) = 2et

g(Hk) =`.Marthe BonamyNombre chromatique et sous-graphes induits8/10 Et si pas de grosse clique ?...pas de petit cycle ?

Theoreme (Mycielski 1955)

8k, il y a un grapheHkavec(Hk)ket!(Hk) = 2.Theoreme (Erd}os 1959)

8k,8`, il y a un grapheHkavec(Hk)k,!(Hk) = 2et

g(Hk) =`.Marthe BonamyNombre chromatique et sous-graphes induits8/10 Et si pas de grosse clique ?...pas de petit cycle ?

Theoreme (Mycielski 1955)

8k, il y a un grapheHkavec(Hk)ket!(Hk) = 2.Theoreme (Erd}os 1959)

8k,8`, il y a un grapheHkavec(Hk)k,!(Hk) = 2et

g(Hk) =`.Marthe BonamyNombre chromatique et sous-graphes induits8/10