# zbMATH — the first resource for mathematics

Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities. (English) Zbl 1213.05240
Summary: We study restricted homomorphism dualities in the context of classes with bounded expansion (which are defined by means of the greatest reduced average densities – grads). 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 “approximate version” of the Hadwiger conjecture.
For Part II, see Eur. J. Comb. 29, No. 3, 777–791 (2008; Zbl 1185.05131).

##### MSC:
 05C83 Graph minors
##### Keywords:
 [1] DeVos, M.; Ding, G.; Oporowski, B.; Sanders, D.P.; Reed, B.; Seymour, P.D.; Vertigan, D., Excluding any graph as a minor allows a low tree-width 2-coloring, Journal of combinatorial theory series B, 91, 25-41, (2004) · Zbl 1042.05036 [2] Diestel, R., Graph theory, (1997), Springer-Verlag [3] Dreyer, P.; Malon, Ch.; Nešetřil, J., Universal $$h$$-colorable graphs without a given configuration, Discrete mathematics, 250, (2002), 245-252 · Zbl 1001.05060 [4] B. Guenin, Edge coloring plane regular multigraphs, manuscript [5] Häggkvist, R.; Hell, P., Universality of A-mote graphs, European journal of combinatorics, 14, 23-27, (1993) · Zbl 0799.05063 [6] Hell, P.; Nešetřil, J., () [7] Hubička, J.; Nešetřil, J., Universal partial order represented by means of trees and other simple graphs, European journal of combinatorics, 26, 5, 765-778, (2005) · Zbl 1060.05092 [8] Naserasr, R., Homomorphisms and edge-coloring of planar graphs, Journal of combinatorial theory series B, 97, 3, 394-400, (2007) · Zbl 1116.05032 [9] Nešetřil, J., Aspects of structural combinatorics, Taiwanese journal of mathematics, 3, 4, 381-424, (1999) · Zbl 0939.05001 [10] Nešetřil, J.; Ossona de Mendez, P., Cuts and bounds, Discrete mathematics, structural combinatorics— combinatorial and computational aspects of optimization, topology and algebra, 302, 1-3, 211-224, (2005) · Zbl 1076.05089 [11] J. Nešetřil, P. Ossona de Mendez, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics (2007), in press (doi:10.1016/j.ejc.2006.07.013) [12] J. Nešetřil, P. Ossona de Mendez, Grad and classes with bounded expansion II. Algorithmic aspects, European Journal of Combinatorics (2007), in press (doi:10.1016/j.ejc.2006.07.014) [13] Nešetřil, J.; Ossona de Mendez, P., Folding, Journal of combinatorial theory series B, 96, 5, 730-739, (2006) · Zbl 1100.05037 [14] Nešetřil, J.; Ossona de Mendez, P., Linear time low tree-width partitions and algorithmic consequences, (), pp. 391-400 · Zbl 1301.05268 [15] Nešetřil, J.; Ossona de Mendez, P., Tree depth, subgraph coloring and homomorphism bounds, European journal of combinatorics, 27, 6, 1022-1041, (2006) · Zbl 1089.05025 [16] Nešetřil, J.; Pultr, A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete mathematics, 22, 287-300, (1978) · Zbl 0388.05039 [17] J. Nešetřil, R. Šámal, Tension continuous maps—their structure and applications, European Journal of Combinatorics (2007), in press (doi:10.1016/j.ejc.2007.11.023) · Zbl 1243.05228 [18] Nešetřil, J.; Švejdarová, I., Diameter of duals are linear, SIAM journal of discrete mathematics, 21, 2, 374-384, (2007) · Zbl 1139.05318 [19] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterizing gaps and good characterizations), Journal of combinatorial theory series B, 80, 80-97, (2000) · Zbl 1024.05078 [20] Nešetřil, J.; Tardif, C., Short answers to exponentially long questions: extremal aspects of homomorphism duality, SIAM journal of discrete mathematics, 19, 4, 914-920, (2005) · Zbl 1105.05025 [21] Szemerédi, E., Regular partitions of graphs, Colloq. int. CNRS, vol. 260, (1978), pp. 399-401 [22] Thomassen, C., A short List color proof of grötzsch theorem, Journal of combinatorial theory series B, 88, 189-192, (2003) · Zbl 1025.05022