Local Cut Lemma 在有向圖的線性印度和 Kγ圖的無圈染色中的應(yīng)用.pdf

1、Local Cut Lemma(簡寫成LCL)是近來由Bernshteyn在Lovasz Local Lemma(簡寫成 LLL)的相關(guān)算法-熵壓縮方法對組合問題應(yīng)用的基礎(chǔ)上，對其進(jìn)行了推廣，它主要是用概率方法來解決圖論中的一些組合優(yōu)化問題。隨著對樹的研究，1970年，Harary[29]提出了圖的線性蔭度這一概念.線性有向森林是指每個部分都是路的有向圖，而有向線性蔭度是指能夠?qū)⒂邢驁DD的所有弧覆蓋的最少線性有向森林個數(shù)，用la(D)表

2、示.對于每一個本正則有向圖D, Nakayama和 Péroche猜測la(D)= d+1,隨后He, Li, B ai和 Sun[31]研究了完全對稱有向圖和大圍長正則有向圖的線性蔭度，并得出對任何d-正則有向圖D,當(dāng)圍長g≥8.0786d時(shí)，la(D)= d+1。通過研究得到，對任何d-正則有向圖，當(dāng) d=1時(shí)，la(D)= d+1;當(dāng) d≥2,且圍長g＞8d時(shí)，la(D)= d+1.圖 G的無圈著色是指正常點(diǎn)染色，并且每個圈上至少

3、包含三種顏色.無圈著色指數(shù)Xa(G)是指滿足無圈著色所用的最少顏色數(shù)。無圈著色最早由Grünbaum[24]提出. Alon, McDiarmid和 Reed在[6]中研究了Kr圖（不包含K2,r+1子圖）的無圈著色指數(shù)，目前最好的結(jié)果是Xa(G)＜1+△(1+√2r+4)。
　　本研究分為五個部分：第一章對圖論起源及其發(fā)展歷程的介紹，重點(diǎn)介紹了圖論各個發(fā)展階段的一些代表性問題。第二章對用到的定義概念進(jìn)行介紹?？偨Y(jié)了一些目前國內(nèi)外