2014/01/07 by Zdenek Dvorak, Dvorak, Zdenek, Robin Thomas +1 · 3 citations
Computer Science · Mathematics · #05C15 (Primary) 05C85 #68Q17 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #acm:05C15 #acm:05C85 #acm:68Q17 #cs.DM #math.CO #msc:05C15 #msc:05C85 #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1401.1399
48 pages, 5 figures; expanded version taking into account referee comments
arxiv created 2016/12/26 · arxiv updated 2016/12/28
A graph H is t-apex if H-X is planar for some subset X of V(H) of size t. For any integer t>=0 and a fixed t-apex graph H, we give a polynomial-time algorithm to decide whether a (t+3)-connected H-minor-free graph is colorable from a given assignment of lists of size t+4. The connectivity requirement is the best possible in the sense that for every t>=1, there exists a t-apex graph H such that testing (t+4)-colorability of (t+2)-connected H-minor-free graphs is NP-complete. Similarly, the size of the lists cannot be decreased (unless P=NP), since for every t>=1, testing (t+3)-list-colorability of (t+3)-connected Kt+4-minor-free graphs is NP-complete.