Note on the Choosability of Bipartite Graphs

Abstract

Let \(B\) be a bipartite graph. We obtain two new results as follows:(1) Suppose that \(u \in V(B)\) is a vertex such that \(N_B(u)\) contains at least \(|N_B(u)| – 1\) odd vertices. Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\) and \(f(v) = \lceil d_B(v)/2 \rceil + 1\) for \(v \in V(B) \setminus u\). Then \(B\) is \(f\)-choosable.(2) Suppose that \(u \in V(B)\) is a vertex such that every vertex in \(N_B(u)\) is odd, and \(v \in V(B)\) is an odd vertex that is not adjacent to \(u\). Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\), \(f(v) = \lceil d_B(v)/2 \rceil\), and \(f(w) = \lceil d_B(w)/2 \rceil + 1\) for \(w \in V(B) \setminus \{u, v\}\). Then \(B\) is \(f\)-choosable.