本文關(guān)鍵詞：平面圖的injective染色

  更多相關(guān)文章： Injective染色 平面圖 圍長(zhǎng) 最大度 最大平均度

【摘要】：本文研究對(duì)象限于簡(jiǎn)單有限圖,對(duì)于圖G的一個(gè)正常頂點(diǎn)k-染色,指的是從G的頂點(diǎn)集合V(G)到顏色集合{1,2,…,k｝的一個(gè)映射c.使得距離為1的點(diǎn)染的顏色也不同,我們用X(G)來(lái)表示滿足上述要求的最小的正整數(shù)k,稱之為圖G的色數(shù)；若圖G的一個(gè)頂點(diǎn)染色Φ稱為Injective染色,那么圖G中有公共鄰點(diǎn)的兩個(gè)頂點(diǎn)染不同的顏色.類似地,Xi(G)稱為圖G的Injective色數(shù),用Xil(G)來(lái)表示Injective列表色數(shù).對(duì)圖G的Injective色數(shù)顯然有△(G)≤χi(G)≤△(G)(△(G)-1)+1,(G≠K2),并且χi(G)≥χ(G).自Hahn等人提出了Injective染色的概念以來(lái),Injective染色的研究熱度始終不減,并成為圖的染色理論中重要的研究方向.總結(jié)起來(lái),人們主要研究了在圖的圍長(zhǎng)、最大度、以及最大平均度等的條件限制下的Injective色數(shù).當(dāng)然,前人提出的許多重大猜想至今仍然是許多海內(nèi)外學(xué)者投身科研的熱情因素之一,其中就包括著名的四色定理.在本文中,主要討論了在不含短圈的條件限制下,平面圖G的Injective色數(shù).第一部分介紹了Injective染色的相關(guān)背景以及研究現(xiàn)狀.作為相對(duì)比較新的平面圖染色研究方向,我們做的主要工作是研究了平面圖的Injective染色數(shù)在圍長(zhǎng)至少為5時(shí)的最優(yōu)值.在后面的章節(jié)里面詳細(xì)討論了Injective染色數(shù)為△+4的充分條件.
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前3條

1 王超;平面圖的injective染色[D];浙江師范大學(xué);2016年

2 陸凱;平面圖的injective染色[D];浙江師范大學(xué);2013年

3 楊勝;平面圖的Injective染色[D];浙江師范大學(xué);2014年

，

本文編號(hào)：1219819