This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1999, with author Galluccio A., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 509  (Previous )  

Anna Galluccio, Goddyn L.A., Hell P.

High girth graphs avoiding a minor are nearly bipartite

ABSTRACT

Let H be a fixed graph. We show that any H?minor free graph of high enough girth has a circularchromatic number arbitrarily close to two. Equivalently, such graphs have homomorphisms into a large odd circuit. In particular, graphs of high girth and of bounded genus or bounded tree width are "nearly bipartite" in this sense. For example, any planar graph of girth at least 16 admits a homomorphism onto a pentagon. We also obtain tight bounds in a few specific cases of small forbidden minors.