邊染色圖的研究是圖論研究的熱點問題之一,邊染色圖的連通性問題是最近十余年以來其中一個十分活躍的課題。給定圖G的一個邊染色,如果該染色使得圖G的任意兩頂點都有一條單色路徑相連,那么稱該邊染色為圖G的一個單色連通染色[4]（簡記為MC-染色）.圖G的單色連通數(shù)是指,使得圖G有單色連通染色的最大顏色數(shù),符號表示為mc（G）.圖的單色連通問題是由Caro&Yuster在2011年提出.近些年來,研究者們對圖的單色連通問題做了一系列研究,其中大多是對圖的單色連通數(shù)的上下界進行刻畫.本文主要研究圖的單色連通數(shù),以及其極值邊染色的特征刻畫.對于任意的連通圖G的單色連通數(shù)都有這樣一個直接的下界:mc（G）≥m（G）-n（G）+2[4].同時Caro&Yuster也給出了一些上界,其中包括mc（G）≤m-n+χ（G）.以下是本文的主要結(jié)構(gòu)和研究內(nèi)容.在第一章中,主要介紹了本論文所涉及的圖論基本概念和術(shù)語,對圖的單色連通數(shù)問題的研究背景和研究現(xiàn)狀進行詳細闡述,并簡要敘述了本學位論文的主要結(jié)果.在第二章中,主要研究了三色圖的單色連通數(shù),并完全解決了相關(guān)問題.在第三章中,主要研究了 r-部圖的... 

【文章來源】：浙江師范大學浙江省

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景
    1.2 基本概念
    1.3 本文主要結(jié)果
第二章 3-色圖的單色連通數(shù)
    2.1 基本定義與引理
    2.2 主要結(jié)果
第三章 r-部圖的單色連通數(shù)
    3.1 基本定義與引理
    3.2 上界1
    3.3 上界2
第四章 圖的單色連通數(shù)達到上界的充分必要性
    4.1 基本定義與引理
    4.2 圖G的單色連通數(shù)達到上界m-n-χ（G）
    4.3 圖G的單色連通數(shù)達到上界m-n+χ（G）-1
參考文獻
攻讀學位期間取得的研究成果
致謝



本文編號：3041768