Grad and classes with bounded expansion III. restricted dualities

2005/08/17 by Jaroslav Nesetril, Patrice Ossona De Mendez
Mathematics · #math.CO #msc:05C75 #msc:05C78

paper · pdf

published as KAM-DIMATIA Series 2005-741 (2005) 1-14

arxiv created 2005/08/17 · arxiv updated 2009/12/01

Abstract

We study restricted homomorphism dualities in the context of classes with bounded expansion. This presents a generalization of restricted dualities obtained earlier for bounded degree graphs and also for proper minor closed classes. This is related to distance coloring of graphs and to the ''approximative version'' of Hadwiger conjecture.

Related

• Grad and classes with bounded expansion I. decompositions
• Grad and Classes with Bounded Expansion II. Algorithmic Aspects
• Vertex-minor-closed classes are χ-bounded
• Induced subdivisions and bounded expansion
• Graph Homomorphism, Monotone Classes and Bounded Pathwidth