F Nous contacter

Multi angle

H 1 Coloring graphs with forbidden induced paths

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

    Loading the player...

    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 rencontre

    Nom du congrès : 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)
    Organisteurs Congrès : Bassino, Frédérique ; Bonomo, Flavia ; Pournin, Lionel ; Valencia-Pabon, Mario ; Vera Lizcano, Juan Carlos
    Dates : 11/09/17 - 15/09/17
    Année de la rencontre : 2017
    URL Congrès : http://conferences.cirm-math.fr/1660.html

    Citation 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


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