圖的染色理論起源于十九世紀中葉被提出的著名的“四色問題”,是圖論中最重要的研究課題之一。近些年來,隨著離散型事物的數(shù)學(xué)模型應(yīng)用的日益廣泛,圖的染色已不僅限于對圖的點染色、邊染色和全染色,各種特征的染色概念相繼出現(xiàn),從而使圖的染色理論研究內(nèi)容也越來越豐富。本文旨在研究特殊的1-平面圖的一些有限制條件的染色問題。若無特別說明,本文所研究的圖均為簡單的,有限的,無向的非空圖。如果一個圖G能畫在平面上使得任意兩條邊之間不產(chǎn)生內(nèi)部交叉(即任何兩條邊之間僅在端點相交),則稱圖G稱為可平面圖。上述這樣一種畫法稱為G的一個平面嵌入。平面圖是指可平面圖的某個平面嵌入。如果一個圖G能畫在平面上使得它的每條邊至多被交叉一次,則稱這個圖為1-可平面圖。滿足上述條件的1-可平面圖的平面嵌入稱為1-平面圖。設(shè)G是一個圖的某個平面嵌入,如果G中出現(xiàn)交叉點,那么每個交叉點都可以與G中的四個頂點(即形成此交叉點的兩條相交邊的四個端點)的點集建立對應(yīng)關(guān)系,記為∧。設(shè)a,b是G中的兩個交叉點,如果∧(a)∩∧(=(?),則稱a與b是相互獨立的。如果圖G能畫在平面上使得其任何兩個交叉點是獨立的,則稱圖G為IC-可平面圖。滿足...

【文章頁數(shù)】：99 頁

【學(xué)位級別】：博士

【文章目錄】：
致謝
摘要
Abstract
變量注釋表
1 緒論
    1.1 基本概念與符號
    1.2 圖的幾類染色及相關(guān)猜想
    1.3 論文主要結(jié)論
2 全染色
    2.1 不含3-圈的1-平面圖的全染色
3 鄰和可區(qū)別全染色
    3.1 IC-平面圖的鄰和可區(qū)別全染色
    3.2 IC-平面圖的鄰和可區(qū)別全染色的緊界
4 無圈邊染色
    4.1 IC-平面圖的無圈邊染色
5 鄰和可區(qū)別邊染色
    5.1 不含3-圈的1-平面圖的鄰和可區(qū)別邊色數(shù)
6 總結(jié)與展望
    6.1 1-平面圖與IC-平面圖的圍長
    6.2 進一步研究的問題
參考文獻
附錄A
作者簡歷
學(xué)位論文數(shù)據(jù)集



本文編號：3801653