（3，4）-雙向正則二部圖的區(qū)間著色.pdf

1、對圖G的邊染顏色l，2，3，…使得圖G的每個點(diǎn)的鄰邊染不同的顏色，稱為圖G的正常邊著色．區(qū)間的定義是數(shù)學(xué)中的普通定義，即連續(xù)的數(shù)序列，如{1，2，3，4}，{α，α+l，α+2，…，α+t}都是區(qū)間，其中α，t為常數(shù)．給定圖G的一個正常邊著色，并且使得每個點(diǎn)相關(guān)聯(lián)的邊的著色構(gòu)成一個區(qū)間，則此著色稱為圖G的一個區(qū)間著色．圖G的一個區(qū)間著色所用的顏色為1，2，3，…，t，且滿足至少有一條邊染顏色i，i=1，2，…，t，則稱為圖G的t-區(qū)間著

2、色．區(qū)間著色產(chǎn)生于一種特定類型的時間表問題，一般來說，判斷一個圖是否具有區(qū)間著色是一個NP-hard問題．不是每一個圖都存在區(qū)間著色的，不存在區(qū)間著色的最簡單的例子是K3.一個二部圖G=(A,B;E)被稱為(α，β)-雙向正則二部圖當(dāng)且僅當(dāng)A中每一個點(diǎn)的度為α，B中每個點(diǎn)的度為β.在這篇文章中我們將證明如果(3，4)-雙向正則二部圖G能劃分為兩個(3，2)-雙向正則二部子圖G1，G7，則G可以6-區(qū)間著色．本文中G1，G2邊不相交，頂點(diǎn)