3-边可染的3-正则图  

Cubic Graphs with 3-edge Coloring of Graphs

作　　者：王艳 周金秋 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)

机构地区：[1]闽南师范大学数学与统计学院,福建漳州363000 [2]江西理工大学理学院,江西赣州341000

出　　处：《数学进展》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。

摘　　要：若一个连通图的每条边都包含在某一完美匹配中,则称之为匹配覆盖图.设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.

关 键 词：3-正则图 3-边可染 BRICK 完美匹配 

分 类 号：O157.5[理学—数学]