کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656661 | 1632972 | 2016 | 24 صفحه PDF | دانلود رایگان |
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.
Journal: Journal of Combinatorial Theory, Series B - Volume 121, November 2016, Pages 284–307