Recognition: unknown
List-coloring apex-minor-free graphs
read the original abstract
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 K_{t+4}-minor-free graphs is NP-complete.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Adjacency labelling for proper minor-closed graph classes
Every proper minor-closed graph class admits a (1+o(1)) log₂ n-bit adjacency labeling scheme, equivalently via an n^{1+o(1)}-vertex universal graph containing all n-vertex members as induced subgraphs.
-
Adjacency labelling for proper minor-closed graph classes
Every proper minor-closed graph class admits an optimal (1+o(1)) log n bit adjacency labeling scheme.
-
Coarse Menger property of quasi-minor excluded graphs and length spaces
Locally finite graphs with an excluded finite minor have the weak coarse Menger property with f depending only on k and g linear in r independent of k.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.