圖的染色理論是圖論研究的核心內(nèi)容,包括頂點(diǎn)染色,邊染色,非正常染色等多個(gè)分支.實(shí)際生活中的儲(chǔ)藏問題、調(diào)度問題以及排課表問題等都可以轉(zhuǎn)化成圖的染色理論來(lái)有效的解決.圖的染色的定義:設(shè)G=(V,E)是一個(gè)圖,k∈N~+,映射f:V→{1,2,···,k}.若對(duì)(?)uv∈E,均有f(u)≠f(u),則稱f為G的一個(gè)正常點(diǎn)染色.如果用V_1,V_2,...,V_k表示G的頂點(diǎn)集的劃分,則圖是k-可染的當(dāng)且僅當(dāng)V_1,V_2,...,V_k是獨(dú)立集.如果放寬這一要求就有了圖的非正常染色的概念:設(shè)d_1,d_2,...,d_k是k個(gè)非負(fù)整數(shù).如果圖G的頂點(diǎn)集可以劃分成V_1,V_2,...,V_k個(gè)子集,使得對(duì)于任意的i=1,2,...,k,V_i的點(diǎn)導(dǎo)出子圖G[V_i]的最大度至多為d_i,則稱圖G是(d_1,d_2,...,d_k)-可染的.雙圈圖的非正常染色,已經(jīng)有許多好的結(jié)果.本文主要研究既不含4-圈也不含6-圈的平面圖的(d_1,d_2)-可染問題.得到如下結(jié)論:(i)如果G是不含4-圈和6-圈的平面圖,則G是(4,4)-可染的.(ii)如果G是不含4-圈和6-圈的平面圖,則G是(3,5)-可染的.
【學(xué)位單位】：江蘇師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類】：O157.5
【文章目錄】：
中文摘要
abstract
第一章 引言
    1.1 背景介紹
    1.2 平面圖非正常染色的研究進(jìn)展與主要結(jié)論
第二章 沒有4-圈和6-圈的平面圖的結(jié)構(gòu)
    2.1 相關(guān)記號(hào)和概念
    2.2 結(jié)構(gòu)引理
第三章 主要結(jié)論及其證明
    3.1 （4,4）-可染
    3.2 （3,5）-可染
第四章 總結(jié)
參考文獻(xiàn)
致謝
作者簡(jiǎn)歷
學(xué)位論文數(shù)據(jù)集

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 徐靈姬;王應(yīng)前;;既不含4-圈又不含6-圈的平面圖的非正常染色[J];中國(guó)科學(xué):數(shù)學(xué);2013年01期

本文編號(hào)：2881589