Anzeige
Erschienen in:
2003 | OriginalPaper | Buchkapitel
Colorings and Homomorphisms of Minor Closed Classes
verfasst von : Jaroslav Nešetřil, Patrice Ossona de Mendez
Erschienen in: Discrete and Computational Geometry
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We relate acyclic (and star) chromatic number of a graph to the chromatic number of its minors and as a consequence we show that the set of all triangle free planar graphs is homomorphism bounded by a triangle free graph. This solves a problem posed in [[15]]. It also improves the best known bound for the star chromatic number of planar graphs from 80 to 30. Our method generalizes to all minor closed classes and puts Hadwiger conjecture in yet another context.