發(fā)布時(shí)間：2018-06-02 22:09

  本文選題：Kempe等價(jià) + Kempe變換　； 參考：《電子與信息學(xué)報(bào)》2017年05期

【摘要】：給定一個(gè)圖G及它的一個(gè)正常頂點(diǎn)著色f,G中任意兩種顏色的頂點(diǎn)導(dǎo)出子圖稱為G的一個(gè)2-色導(dǎo)出子圖,該2-色導(dǎo)出子圖的分支稱為G的一個(gè)2-色分支。Kempe變換是指將圖G的某個(gè)2-色分支實(shí)施顏色互換。若兩個(gè)著色之間可通過若干次Kempe變換達(dá)到對方,則這兩個(gè)著色是Kempe等價(jià)的。Mohar猜想當(dāng)k33時(shí),對于任意的連通k-正則圖G,若G不是完全圖,則G的所有k-著色是Kempe等價(jià)的。Feghali等人解決了k=3時(shí)的情況,當(dāng)k34時(shí),此猜想尚未解決。該文研究了k=4時(shí)的情況,證明了:(1)若G是一個(gè)連通度小于3的4-正則圖,則G的所有4-著色是Kempe等價(jià)的;(2)若G是4-正則圖,且含有與4-輪或近5-階完全圖同構(gòu)的子圖,則G的所有4-著色是Kempe等價(jià)的;(3)若G是一個(gè)3-連通4-正則圖,且G存在一個(gè)頂點(diǎn)x和一個(gè)4-著色f,滿足x的鄰域中有3個(gè)或4個(gè)頂點(diǎn)在f下著相同顏色,則G的所有4-著色是Kempe等價(jià)的。
[Abstract]:Given a graph G and a vertex derived subgraph of any two colors in its normal vertex coloring fG is called a 2-chromatic derived subgraph of G. The branch of the 2-chromatic derived subgraph is called a 2-chromatic branch of G. Kempe transformation means that some 2-chromatic branch of G is interchanged. If the two coloring can reach each other by several Kempe transformations, then the coloring is Kempe equivalent. Mohar conjectures that for any connected kregular graph G when k33, if G is not a complete graph, Then all k-coloring of G is Kempe equivalent. Feghali et al. Solved the case of k = 3. When k34, this conjecture has not been solved. In this paper, we study the case of k = 4 and prove that if G is a 4-regular graph with connectivity less than 3, then all 4-coloring of G is Kempe equivalent) if G is a 4-regular graph and contains a subgraph which is isomorphic to a 4- ring or nearly 5-order complete graph. Then all 4-coloring of G is Kempe equivalent) if G is a 3-connected 4-regular graph, and G has a vertex x and a 4-coloring f, it satisfies that there are three or four vertices in the neighborhood of x with the same color under f. Then all the 4-coloring of G is Kempe equivalent.
【作者單位】： 北京大學(xué)信息科學(xué)技術(shù)學(xué)院;北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室;
【基金】：國家973計(jì)劃項(xiàng)目(2013CB329600) 國家自然科學(xué)基金(61372191,61472012,61472433,61572046,61502012,61572492,61572153,61402437)~~
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 宋曉新;關(guān)于3正則圖的三匹配交猜想(I)[J];數(shù)學(xué)研究;2002年04期

2 宋曉新;關(guān)于3正則圖的三匹配交猜想 (Ⅱ)(英文)[J];數(shù)學(xué)季刊;2002年04期

3 嚴(yán)謙泰;關(guān)于2K階K正則圖強(qiáng)協(xié)調(diào)性的研究[J];安陽師范學(xué)院學(xué)報(bào);2003年02期

4 嚴(yán)謙泰;關(guān)于5-正則圖的強(qiáng)協(xié)調(diào)性[J];大學(xué)數(shù)學(xué);2003年02期

5 閆桂英,許保光,吉日木圖;關(guān)于3-正則圖的路分解[J];系統(tǒng)科學(xué)與數(shù)學(xué);2004年02期

6 鐘波,謝挺;關(guān)于正則圖的路分解[J];西華大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

7 周后卿;徐立新;;正則圖的強(qiáng)積的秩[J];吉首大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年01期

8 梁志和;;完全圖循環(huán)分解成2-正則圖[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2008年06期

9 南小康;;3-正則圖的1-因子與割邊數(shù)[J];蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年S1期

10 李光暖;許寶剛;;關(guān)于正則圖存在平衡劃分的一些結(jié)果[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯;2009年03期

相關(guān)會議論文 前2條

1 ;Hamilton Circuits in Cubic Polyhex Graphs[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（下卷）[C];2000年

2 師海忠;;正則圖連通圈:多種互連網(wǎng)絡(luò)的統(tǒng)一模型[A];中國運(yùn)籌學(xué)會第十屆學(xué)術(shù)交流會論文集[C];2010年

相關(guān)博士學(xué)位論文 前6條

1 文飛;若干圖類的譜特征問題研究[D];新疆大學(xué);2015年

2 程希明;只有三個(gè)不同特征值的圖[D];中國科學(xué)技術(shù)大學(xué);2016年

3 汪定國;正則圖的獨(dú)立集與團(tuán)橫貫[D];上海大學(xué);2013年

4 張翠;s-正則圖和Hamilton圖[D];北京交通大學(xué);2011年

5 劉奮進(jìn);圖鄰接譜確定問題的一些研究[D];新疆大學(xué);2012年

6 邵澤輝;Ramsey理論中圖的構(gòu)造與計(jì)算[D];華中科技大學(xué);2008年

相關(guān)碩士學(xué)位論文 前10條

1 秦艷麗;9度1—正則Cayley圖的分類[D];廣西大學(xué);2015年

2 李玉萍;三正則雙軌道圖的連通性和極大非正則圖[D];新疆大學(xué);2015年

3 王兆;五正則圖的斜能量研究[D];青海師范大學(xué);2015年

4 嚴(yán)卉;（n-4）—正則圖的約束數(shù)的界[D];南京師范大學(xué);2015年

5 顏娟;第Ⅱ類正則圖的色特征[D];新疆大學(xué);2006年

6 蘭培挺;一些4-正則圖最優(yōu)擴(kuò)張的演化[D];北京交通大學(xué);2007年

7 趙承業(yè);三正則圖及其相關(guān)圖的交叉數(shù)問題[D];大連理工大學(xué);2002年

8 郝欣;具有相同路徑層矩陣不同構(gòu)的r-正則圖[D];大連理工大學(xué);2004年

9 周后卿;正則圖在某些二元運(yùn)算下的秩[D];湖南師范大學(xué);2006年

10 潘克亮;非正則圖的最大特征值的若干結(jié)果[D];華東師范大學(xué);2012年

，

本文編號：1970377