定向圖的直徑和平面圖的不完全選色性.pdf

1、對(duì)于圖H(m，n)=Km∨Kn，給圖定向使得它的直徑最小.這里m≥2和n≥1時(shí)，論文有這樣的結(jié)論：(1)(m是奇數(shù)時(shí))對(duì)于m=2p+1，p≥1這種情況，當(dāng)n≤(「mm/2」)-m時(shí)圖的直徑是2，當(dāng)n≥(「mm/2)時(shí)候是3.(2)(m是偶數(shù)時(shí))對(duì)于m=4p+2，p≥0這種情況，如果n≤(mm/2)-m/2，那么直徑是2，其他的時(shí)候是3,對(duì)于m=4p，p≥1這種情況，如果n≤(mm/2)-m/2一1，那么直徑是2，其他的時(shí)候是3.

2、 論文還討論了關(guān)于平面圖不完全選色的問題.若對(duì)任一定點(diǎn)給定k種顏色的列表，染色時(shí)每個(gè)頂點(diǎn)的顏色只能從自身的顏色列表中選擇且每個(gè)頂點(diǎn)至多有d個(gè)鄰點(diǎn)和它染相同的顏色，總存在圖G的一個(gè)頂點(diǎn)的正常著色，則圖G稱為(k，d)*-可選色的.在第二章中證明了一個(gè)周長(zhǎng)不小4且不含5-，6-圈的平面圖，如果它至多有4個(gè)4-圈，那么這個(gè)圖是(2，2)*-可選色的.還證明了一個(gè)周長(zhǎng)不小4且不含5-，6-圈的平面圖，如果它含有4-圈的個(gè)數(shù)至多為5，那么這個(gè)圖是