论文部分内容阅读
假设G是一个图,r是一个实数,如果对于任意的a/b≥r,G是（a,b）—可选的（在线（a,b）—可选的）,则说G是强分数r-可选的（强分数在线r-可选的）.图G的强分数选择数chfs（G）被定义为chfs（G）=inf{r ∈ R:G是强分数r-可选的}.图G的强分数在线选择数χf,Ps（G）被定义为χf,Ps（G）=inf{r ∈ R:G是强分数在线r-可选的}.本学位论文主要介绍并探究图的强分数选择数chfs（G）和图的强分数在线选择数χf,Ps（G）.首先我们证明了对于任意一个有限图G,chfs（G）和χf,Ps（G）都是有理数,而且对于任意的满足p≥2q且2p/2q+1≤[p/q]的正整数p和q,都存在图G使得chfs（G）=χf,Ps（G）p/q.其次我们研究了图的强分数选择数chfs（G）和强分数在线选择数χf,Ps（G）的上界.特别地,对于一些特殊图类,我们主要证明如下结果:1.完全二部图.我们应用超图的2-染色技巧证明了对于任意n个点的完全二部图G,都有chfs（G）≤1+[log2n].2.完全多部图.2020年,Yan证明了如果对于任意正整数m,图G都是在线（km,m）-可选的,|V（G）|≤k+k/t-1,那么对于任意正整数m,图G（?）Kt是在线（（k+1）m,m）-可选的.但是该证明中有一些瑕疵,我们修正了该证明,并利用该理论证明了对于完全多部图K2*k,有chfs(K2*k)=χf,Ps(K2*k)=k.3.子式-封闭的图类.我们证明了对于任意图H,e>0,都存在一个正整数g使得任意围长至少为g且不含H子式的图G,都有chfs（G）≤2+∈.据此,我们证明了每一个围长至少是g（g≥ 6）的平面图的强分数选择数都不超过2+1/[（g+6）/12].4.在线3-可选-临界图.这些图本身都不是在线2-可选的,但任意一个的真子图都是.我们证明了对于这一类图中任意图G,如果它是奇圈（假设长度是2k+1）,那么χf,ps（G）=2+1/k.对于非奇圈的在线3-可选-临界图G,chfs（G）≤χf,Ps（G）≤5/2.一族图g的强分数选择数被定义为其所含的所有图的强分数选择数的上确界.假设我们用P表示平面图类,用Pk1,,kq表示不含kχf,Psi-圈长的平面图,其中i=1,,q.我们证明了3+1/2 ≤ chfs（P4）≤4,chfs（P5）=chfs（P6）=4,3+1/12 ≤ chfs(P4,5)≤ 4以及chfs（P）≥4+1/3.其中最后一个结果改进了[X.Zhu.Multiple list colouring of planar graphs.J.Combin.Theory Ser.B,122:794-799,2017]中的下界4+2/9.我们着重研究了 3-可选-临界图的强分数选择数.这类图的特点是它们本身不是3-可选的但是其中任意一个的真子图都是.在1998年,Voigt刻画了这类图,包括:（1）奇圈;（2）两个点不交的偶圈被一条路连接;（3）两个偶圈共享一个点;（4）Θr,s,t图,其中r ≥1,s,t≥3,且r,s,t同奇偶;（5）Θ2,2,2,2p图,其中p≥1.1996年,Tuza和Voigt证明了对于任意正整数m,Θ2,2,2,2都是（4m,2m）-可选的.1998年,Voigt发现了更多满足该性质的二部3-可选-临界图,并猜想对于任意正整数m,每一个二部3-可选-临界图都是（4m,2m）-可选的.如果这个猜想正确的话,那么每一个二部3-可选-临界图的强分数选择数都是2.然而,在2017年,这个猜想被Meng,Puleo和Zhu否定了.他们证明如果G=Θr,s,t,其中r,s,t同奇偶,且min{r,s,t}≥3,或者G=Θ2,2,2,2p,其中p≥2,那么G不是（4,2）-可选的.不过剩余所有类的二部3-可选-临界图都是（4,2）-可选的.我们加强了Meng,Puleo和Zhu的结果,证明了对于任意正整数m,剩余所有类的二部3-可选-临界图都是（4m,2m）-可选的.另一方面,我们证明了对于那些非-（4,2）-可选的二部3-可选-临界图,它们当中任一个图对于任意正整数m都是（2m+1,m）-可选的.据此,我们完全确定了 3-可选-临界图的强分数选择数:如果G是一个长度为2k+1的奇圈,那么chfs（G）=χf,Ps（G）=2+1/k,而对于所有剩余的图G,都有chfs（G）=2.