On $(2,t)$-Choosability of Triangle-Free Graphs

Wongsakorn Charoenpanitseri


A $(k,t)$-list assignment $L$ of a graph $G$ is a mapping which assigns a set of size $k$ to each vertex $v$ of $G$ and $|\bigcup_{v\in V(G)}L(v)|=t$. A graph $G$ is $(k,t)$-choosable if $G$ has a proper coloring $f$ such that $f(v)\in L(v)$ for each $(k,t)$-list assignment $L$.

In 2011, Charoenpanitseri, Punnim and Uiyyasathian proved that every $n$-vertex graph is $(2,t)$-choosable for $t\geq 2n-3$ and every $n$-vertex graph containing a triangle is not $(2,t)$-choosability for $t\leq 2n-4$. Then a complete result on $(2,t)$-choosability of an $n$-vertex graph containing a triangle is revealed. Moreover, they showed that an $n$-vertex triangle-free graph is $(2,t)$-choosable for $t\geq 2n-6$.

In this paper, we first prove that an $n$-vertex graph containing $K_{3,3}-e$ is not $(2,t)$-choosable for $t\leq 2n-7$. Then we deeply investigates $(2,t)$-choosablity of an $n$-vertex graph containing neither a triangle nor $K_{3,3}-e$.

Full Text:


DOI: http://dx.doi.org/10.5539/jmr.v5n3p11

Journal of Mathematics Research   ISSN 1916-9795 (Print)   ISSN 1916-9809 (Online)

Copyright © Canadian Center of Science and Education

To make sure that you can receive messages from us, please add the 'ccsenet.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.