E) be a bipartite graph and D an orientation of G with out-degree sequence (d -D ++(v) ｜v∈V) . Let f -D(v)=d -D ++(v)+1 be a function of integers defined on V . In this paper
by using algebra method we prove that G is f -D -choosable. In particular
G is ([JB([][SX(]Δ(G)[]2[SX)][JB)]]+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.
关键词
Keywords
references
Erdo。s P,Rubin A L and Taylor H.Choosability in graphs[J].In:Proc.West Coast Conference on Combinatorics,Graph Theory and Computing,Arcata,1979,26:125-157.
Vizing V G.Coloring the vertices of a graph in prescribed colors[J].Diskret.Anal.1976,29:3-10.
Alon N.Restricted colorings of graphs,Surveys in Combinatorics,Proc.14th-British Combinatorial Conference[C].London Mathematical Society Lecture Notes Series,1993,187:1-33.
Tuza Z.Graph colorings with local constraints-a survey[J].Discussiones Mathematicae Graph Theorey,1997,17(2):161-228.
Bolloba。s B.Modern Graph Theory[M].Springer-Verlag New York,Inc.,1998.
Alon N and Tarsi M.Colorings and orientations of graphs[J].Combina torics,1992,12:125-134.
京公网安备11010802024621