List colorings of $K_5$-minor-free graphs with special list assignments

Details List colorings of $K_5$-minor-free graphs with special list assignments List colorings of $K_5$-minor-free graphs with special list assignments

2011-05-12

arxiv.org/abs/1105.2532v1

Mathematics

Combinatorics

14 pages, 2 figures, 2 tables

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

List colorings of $K_5$-minor-free graphs with special list assignments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with List colorings of $K_5$-minor-free graphs with special list assignments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and List colorings of $K_5$-minor-free graphs with special list assignments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-497399