Article ID Journal Published Year Pages File Type
4654984 European Journal of Combinatorics 2006 13 Pages PDF
Abstract

We study the homomorphism (coloring) order induced on minor closed classes. In [J. Hubička, J. Nešetřil, Finite Paths are Universal, ITI Series 2003-129, Charles University, 2003. Order (in press)], the minor closed class PP of directed paths is shown to be universal and in [J. Nešetřil, X. Zhu, Path homomorphisms, Proc. Comb. Phil. Soc. (1996) 207–220], PP is shown to contain a dense subset. In this note we prove that PP is a unique minimal class of oriented graphs which is both universal and dense. Moreover, we show a dichotomy result for any minor closed class KK of directed trees: KK is either universal or it is well-quasi-ordered (wqo). We also prove structure theorems about series–parallel graphs (SPG), in an attempt to determine the minimal universal and dense minor closed classes of undirected graphs. We show the non-existence of universal classes in certain subclasses of SPG. Also for basic graphs in the class of SPG, we show that there is a linear time algorithm that decides whether such a graph is core or not. We also give a constructive description of arbitrary 2-connected graphs in SPG.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,