胡琳, 王国平. [2,3]-可选的完全二部图的刻划(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2004, (4).DOI：
[2,3]-可选的完全二部图的刻划(英文)
摘要
目前
所有 2 -可选的图在 [2 ]中已给出
但对 3-可选的图
即使是对 3-可选的二部图的分类仍未完成 .在[3]和 [4]中有一些相关结果 .事实上
这是一项困难的工作 .因此
在本文中
我们考虑了条件较弱一类图的分类问题
即对所有 [2
3]-可选的完全二部图进行了分类 .我们证明了 K3
7、K8
2 、 K1
n、K2
n和 Km
n( m + n≤ 9且当 n=4时 m≠ 5 )是所有的 [2
3]-可选的完全二部图
它对进一步刻划 3-可选的完全二部图有一定帮助
Abstract
Although the 2-choosable graphs have been fully classified in [2]
the 3-choosable graphs have not been classified yet
even if 3-choosable bipartite graphs. There are a few of results related it (see references [3] and [4]) and it seems difficult to completely classify the 3-choosable graphs. In this paper
we consider a weak problem
that is
to classify the [2
3]-choosable complete bipartite graphs. We prove that K3
7
K8
2 K1
n
K2
n(n≥1) and Km
n (m+n≤9 and m≠5 when n=4) are all [2
3]-choosable complete bipartite graphs
and thus the [2
3]-choosable complete bipartite graphs are completely characterized here
which
we consider
will be useful in the further research of the 3-choosable bipartite graphs.
关键词
Keywords
references
VizingV G.Vertex colorings with given colors( inRussian)[J].MetodyDiskretAnaliz,1976,29:3-10.
ErdosP,RubinA L andTaylorH Choosability in graphs[A].In:Proc.WestCoastConference onCombinatorics,GraphTheory andComputing,Arcata,Congr.Num[C].1979,26:125-157.
TuzaZ.Graph colorings with local constraints-a survey[J].DiscussionesMathematicaeGraphTheory,1997,17:161-228.
GravierS,MaffrayF.Graph whose choice numberis equal to theirchromatic number[J].JGraphTheory,1998,27:87-97.
京公网安备11010802024621