m
• E

F Nous contacter

0

Multi angle

H 1 Coloring graphs with forbidden induced paths

Auteurs : Chudnovsky, Maria (Auteur de la Conférence)
CIRM (Editeur )

Résumé : The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a polynomial time algorithm to 3-color (or in general $k$-color) an $H$-free graph? 2) For which graphs $H$ are there finitely many 4-critical $H$-free graphs? This talk will survey recent progress on these questions, and in particular give a complete answer to the second one.

Keywords : Graph coloring; induced subgraphs; coloring algorithms

Codes MSC :
05C15 - Coloring of graphs and hypergraphs
05C85 - Graph algorithms

 Informations sur la Vidéo Langue : Anglais Date de publication : 14/09/17 Date de captation : 12/09/17 Collection : Research talks ; Combinatorics Format : MP4 Durée : 00:54:57 Domaine : Combinatorics Audience : Chercheurs ; Doctorants , Post - Doctorants Download : https://videos.cirm-math.fr/2017-09-12_Chudnovsky.mp4 Informations sur la rencontre Nom de la rencontre : IX Latin and American algorithms, graphs and optimization symposium (LAGOS 2017) / 9e symposium latino et americain des algorithmes, graphes et de l'optimisation (LAGOS 2017)Organisateurs de la rencontre : Bassino, Frédérique ; Bonomo, Flavia ; Pournin, Lionel ; Valencia-Pabon, Mario ; Vera Lizcano, Juan CarlosDates : 11/09/17 - 15/09/17 Année de la rencontre : 2017 URL Congrès : http://conferences.cirm-math.fr/1660.htmlCitation Data DOI : 10.24350/CIRM.V.19221303 Cite this video as: Chudnovsky, Maria (2017). Coloring graphs with forbidden induced paths. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19221303 URI : http://dx.doi.org/10.24350/CIRM.V.19221303

### Voir aussi

Bibliographie

1. Chudnovsky, M. (2014). Coloring graphs with forbidden induced subgraphs, Procedings of the ICM - https://web.math.princeton.edu/~mchudnov/ICM.pdf

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée

0
Z