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

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

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



本文編號：3747420