Source author record

Anja Pruchnewski

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

1works
1topics
3close collaborators

Published work

1 publications

preprint2011arXiv

List colorings of K5K_5-minor-free graphs with special list assignments

A {\it list assignment} LL of a graph GG is a function that assigns a set (list) L(v)L(v) of colors to every vertex vv of GG. Graph GG is called {\it LL-list colorable} if it admits a vertex coloring ϕϕ such that ϕ(v)∈L(v)ϕ(v)\in L(v) for all v∈V(G)v\in V(G) and ϕ(v)≠ϕ(w)ϕ(v)\not=ϕ(w) for all vw∈E(G)vw\in E(G). The following question was raised by Bruce Richter. Let GG be a planar, 3-connected graph that is not a complete graph. Denoting by d(v)d(v) the degree of vertex vv, is GG LL-list colorable for every list assignment LL with ∣L(v)∣=min⁡{d(v),6}|L(v)|=\min \{d(v), 6\} for all v∈V(G)v\in V(G)? More generally, we ask for which pairs (r,k)(r,k) the following question has an affirmative answer. Let rr and kk be integers and let GG be a K5K_5-minor-free rr-connected graph that is not a Gallai tree (i.e., at least one block of GG is neither a complete graph nor an odd cycle). Is GG LL-list colorable for every list assignment LL with ∣L(v)∣=min⁡{d(v),k}|L(v)|=\min\{d(v),k\} for all v∈V(G)v\in V(G)? We investigate this question by considering the components of G[Sk]G[S_k], where Sk:={v∈V(G)∣d(v)<k}S_k:=\{v\in V(G) | d(v)<k\} is the set of vertices with small degree in GG. We are especially interested in the minimum distance d(Sk)d(S_k) in GG between the components of G[Sk]G[S_k].

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.