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

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

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

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