关于二部图和欧拉图的列表着色(英文)

On the List Colorings of the Bipartite Graphs and Euler Graphs

设G=(V,E)是二部图,D是G的一个定向具有出度序列(dD+(v)v∈V).设fD(v)=dD+(v)+1是定义在V上的整数函数.在本文中我们利用代数方法证明了G是fD-可选的,并由此推出G是Δ(2G)+1)-可选的,2d-正则偶图是(d+1)-可选的.定义了欧拉图的半度-可选概念,并给出了一类半度-可选的欧拉非偶图.最后,提出了刻化半度-可选的欧拉图.

Let G = （V,E） be a bipartite graph and Dan orientation of Gwith out-degree sequence （dv＋ （v） ｜v ∈ V） . Let fn（v）=dD^＋ （v） ＋ 1 be a function of integers defined onV. In this paper, by using algebra method we prove that G is fD-choosable. In particular, G is （[（（△（G））/2]＋1） -choosable, 2d-regular bipartite is （d ＋ 1） - choosable. We also define half-degree choosable for Euler graphs and give a class of such graphs that are not bipartite. At last we suggest a problem to characterize the half-degree choosable Euler graphs.