若一個(gè)連通圖的每條邊都包含在某一完美匹配中,則稱之為匹配覆蓋圖.設(shè)G是一個(gè)3-連通圖,若去掉G的任意兩個(gè)頂點(diǎn)后得到的子圖仍有完美匹配,則稱G是一個(gè)brick.而brick的重要性在于它是匹配覆蓋圖的組成結(jié)構(gòu)因子.3-邊可染3-正則5的刻畫(huà)問(wèn)題是一個(gè)NP-完全問(wèn)題.本文將此問(wèn)題規(guī)約到3-正則匹配覆蓋圖上,進(jìn)而規(guī)約到其組成結(jié)構(gòu)因子brick上.我們證明了:一個(gè)3-正則圖是3-邊可染的當(dāng)且僅當(dāng)它的所有brick是3-邊可染的.

【文章頁(yè)數(shù)】：5 頁(yè)

【文章目錄】：
0 Introduction
1 The Perfect Matching Polytope
2 Main Results



本文編號(hào)：3747420