Coloring immersion-free graphs

A graph H is immersed in a graph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. The notion of an immersion is quite similar to the well-known notion of a minor, as structural approach inspired by the theory of graph minors has been extremely successful in immersions.Hadwiger's conjecture on graph coloring, generalizing the Four Color Theorem, states that every loopless graph without a KkKk-minor is (k−1)(k−1)-colorable, where KkKk is the complete graph on k vertices. This is a long standing open problem in graph theory, and it is even unknown whether it is possible to determine ck  -colorability of KkKk-minor-free graphs in polynomial time for some constant c. In this paper, we address coloring graphs without H-immersion. In contrast to coloring H-minor-free graphs, we show the following:1.there exists a fixed-parameter algorithm to decide whether or not a given graph G without an immersion of a graph H of maximum degree d   is (d−1)(d−1)-colorable, where the size of H is a parameter. In fact, if G   is (d−1)(d−1)-colorable, the algorithm produces such a coloring, and2.for any positive integer k   (k≥6k≥6), it is NP-complete to decide whether or not a given graph G   without a KkKk-immersion is (k−3)(k−3)-colorable.