圖的若干染色第1頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月1.鄰點(diǎn)可區(qū)別邊染色第2頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月定義1：對(duì)于一個(gè)簡(jiǎn)單圖,

是一個(gè)正常邊染色，如果滿足:

這里則我們稱為的鄰點(diǎn)可區(qū)別邊染色,簡(jiǎn)記為,且稱為的鄰點(diǎn)可區(qū)別邊色數(shù).第3頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月猜想1.1:對(duì)于無(wú)孤立邊的簡(jiǎn)單圖,且,則

這里表示的最大度.(張忠輔等，A.M.L.2002)第4頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月進(jìn)展

當(dāng)及二部圖時(shí),猜想為真.

當(dāng)時(shí),第5頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月與全色數(shù)的關(guān)系

設(shè)是正則圖(),則

(1)

當(dāng)且僅當(dāng)

(2)猜想1.2:

當(dāng)且僅當(dāng)其中表示的全色數(shù).第6頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月2.鄰點(diǎn)可區(qū)別全染色第7頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

定義2:對(duì)于一個(gè)簡(jiǎn)單圖,

是一個(gè)正常全染色，如果滿足:,這里則我們稱為的鄰點(diǎn)可區(qū)別全染色,簡(jiǎn)記為,且

稱為的鄰點(diǎn)可區(qū)別全色數(shù).第8頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

猜想2:對(duì)于簡(jiǎn)單圖,有

(“中科”

2004(5))

第9頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月進(jìn)展當(dāng)時(shí),猜想為真.

(JourCombOpti2007(14),D.M308(2008))

當(dāng)時(shí),猜想也為真.

第10頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月3.點(diǎn)可區(qū)別全染色第11頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

定義3:對(duì)于一個(gè)簡(jiǎn)單圖

,

是一個(gè)

正常全染色，若滿

足:

,這里

則我們稱為的點(diǎn)可區(qū)別全染色,簡(jiǎn)記為

,且

稱為

的點(diǎn)可區(qū)別全色數(shù).第12頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

猜想3:設(shè)是一個(gè)簡(jiǎn)單圖,則這里表示的組合全度.(ArsComb87(2008))

第13頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月4.鄰點(diǎn)強(qiáng)可區(qū)別全染色第14頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月定義4:設(shè)是階數(shù)不小于3的簡(jiǎn)單連通圖,是正常全染色,

若滿足:這里我們稱為的鄰點(diǎn)強(qiáng)可區(qū)別全染色,簡(jiǎn)記為且

稱為的鄰點(diǎn)強(qiáng)可區(qū)別全色數(shù).第15頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

猜想4:

(1)若為階數(shù)不小于3的簡(jiǎn)單連通圖,則有

等號(hào)成立當(dāng)且僅當(dāng)為的完全圖.(2)若是最大度為的平面圖,則

(“中科”20079)第16頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月5.一般鄰點(diǎn)可區(qū)別全染色第17頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

定義5:對(duì)于簡(jiǎn)單圖,是從到的映射,

若滿足:對(duì)這里我們稱為的一般鄰點(diǎn)可區(qū)別全染色.簡(jiǎn)記為,且稱為的一般鄰點(diǎn)可區(qū)別全色數(shù).第18頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月猜想5:假設(shè)是一個(gè)簡(jiǎn)單圖,

且,則

第19頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月6.一般點(diǎn)可區(qū)別全染色第20頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月

定義6:對(duì)于簡(jiǎn)單圖,是一個(gè)從到的映射,若滿足:

這里我們稱為的一般點(diǎn)可區(qū)別全染色,簡(jiǎn)記為且稱為的一般點(diǎn)可區(qū)別全色數(shù).

第21頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月猜想6:

(1)設(shè)是一個(gè)n個(gè)頂點(diǎn)的簡(jiǎn)單圖且,則

(2)設(shè)是一個(gè)簡(jiǎn)單圖,則

第22頁(yè)，課