摘要
若一个连通图的每条边都包含在某一完美匹配中,则称之为匹配覆盖图.设G是一个3-连通图,若去掉G的任意两个顶点后得到的子图仍有完美匹配,则称G是一个brick.而brick的重要性在于它是匹配覆盖图的组成结构因子.3-边可染3-正则5的刻画问题是一个NP-完全问题.本文将此问题规约到3-正则匹配覆盖图上,进而规约到其组成结构因子brick上.我们证明了:一个3-正则图是3-边可染的当且仅当它的所有brick是3-边可染的.
A graph is called matching covered if it is connected and every edge belongs to a perfect matching.A 3-connected graph G is called a brick if the graph obtained from it by deleting any two vertices has a perfect matching.The importance of bricks stems from the fact that they are building blocks of matching covered graphs.In this paper,we reduce the NP-complete problem of characterizing the 3-edge-colorable cubic graphs to matching covered cubic graphs,then to its bricks.Namely,a cublc graph is 3-edge-colorable if and only if all its bricks are 3-edge-colorable.
作者
王艳
周金秋
WANG Yan;ZHOU Jinqiu(School of Mathematics and Statistics,Minnan Normal University,Zhangzhou,Fujian,363000,P.R.China;Faculty of Science,Jiangxi University of Science and Technology,Ganzhou,Jiangxi,341000,P.R.China)
出处
《数学进展》
CSCD
北大核心
2020年第4期413-417,共5页
Advances in Mathematics（China）
基金
NSFC(No.11671186)
NSF of Fujian(No.2017J01404)
Institute of Meteorological Big Data-Digital Fujian and Fujian Key Laboratory of Data Science and Statistics。
