Published by Canadian Center of Science and Education On (2, t)-Choosability of Triangle-Free Graphs

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 |⋃v∈V(G) L(v) | = t. A graph G is (k, t)-choosable if G has a proper coloring f such that f (v) ∈ 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 ≥ 2n − 3 and every n-vertex graph containing a triangle is not (2, t)-choosability for t ≤ 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 ≥ 2n − 6. In this paper, we first prove that an n-vertex graph containing K3,3 − e is not (2, t)-choosable for t ≤ 2n − 7. Then we deeply investigates (2, t)-choosablity of an n-vertex graph containing neither a triangle nor K3,3 − e