Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2020, Vol. 49(4): 413-417
研究论文
3-边可染的3-正则图
Cubic Graphs with 3-edge Coloring of Graphs

王艳1, 周金秋2
WANG Yan1,*, ZHOU Jinqiu2

1.闽南师范大学数学与统计学院, 漳州, 福建, 363000;
2.江西理工大学理学院, 赣州, 江西, 341000
1. School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, Fujian, 363000, P. R. China;
2. Faculty of Science, Jiangxi University of Science and Technology, Ganzhou, Jiangxi, 341000, P. R. China

收稿日期: 2019-06-01
出版日期: 2020-08-11
2020, Vol. 49(4): 413-417
DOI: 10.11845/sxjz.2019059b


PDF
[158 KB]
58
下载
192
浏览

引用导出
0
    /   /   推荐

摘要 若一个连通图的每条边都包含在某一完美匹配中, 则称之为匹配覆盖图.设$G$是一个3-连通图, 若去掉$G$的任意两个顶点后得到的子图仍有完美匹配, 则称$G$是一个brick.而brick的重要性在于它是匹配覆盖图的组成结构因子. 3-边可染3- 正则图的刻画问题是一个NP-完全问题.本文将此问题规约到3-正则匹配覆盖图上, 进而规约到其组成结构因子brick上.我们证明了: 一个3-正则图是3-边可染的当且仅当它的所有brick是3-边可染的.
关键词 3-正则图3-边可染brick完美匹配    
Abstract: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 cubic graph is 3-edge-colorable if and only if all its bricks are 3-edge-colorable.
Key wordscubic graph    3-edge-colorable    brick    perfect matching
PACS:  O157.5  
通讯作者: E-mail: * wangyan@mnnu.edu.cn   
[1] Appel, K. and Haken, W., Every planar map is four colorable, I. Discharging, Illinois J. Math., 1977, 21(3): 429-490.
[2] Appel K., Haken W. and Koch J., Every planar map is four colorable, II. Reducibility, Illinois J. Math., 1977, 21(3): 491-567.
[3] De Carvalho, M.H., Lucchesi, C.L. and Murty, U.S.R., The perfect matching polytope and solid bricks, J. Combin. Theory Ser. B, 2004, 92(2): 319-324.
[4] Edmonds J.,Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bur. Standards Sect. B, 1965, 69B: 125-130.
[5] Edmonds J., Lovász L. and Pulleyblank W.R., Brick decompositions and the matching rank of graphs, Combinatorica, 1982, 2(3): 247-274.
[6] Holyer I.,The NP-completeness of edge-coloring, SIAM J. Comput., 1981, 10(4): 718-720.
[7] Kochol M.,Krivo$\breve{n}$áková, N. and Smejová, S., Edge-coloring of multigraphs, Discrete Math., 2005, 300(1/2/3): 229-234.
[8] Kothari N., de Carvalho M.H., Little C.H.C. and Lucchesi C.L., On essentially 4-edge-connected cubic bricks,2018, arXiv:1803.08713v1.
[9] Lovász L.,Matching structure and the matching lattice, J. Combin. Theory Ser. B, 1987, 43(2): 187-222.
[10] Lovász, L. and Plummer, M.D., Matching Theory, North-Holland Mathematics Studies, Vol. 121, Amsterdam: North-Holland Publishing Co., 1986.
[11] Lucchesi C.L., de Carvalho, M.H., Kothari, N. and Murty, U.S.R., On two unsolved problems concerning matching covered graphs, SIAM J. Discrete Math., 2018, 32(2): 1478-1504.
[12] Robertson N., Sanders D., Seymour P. and Thomas R., The four-colour theorem, J. Combin. Theory Ser. B, 1997, 70(1): 2-44.
[13] Vazirani, V.V. and Yannakakis, M., Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Discrete Appl. Math., 1989, 25(1/2): 179-190.
[14] Vizing V.G.,On an estimate of the chromatic class of a $p$-graph, Diskret. Analiz, 1964, 3: 25-30 (in Russian).
[15] Wang Y.,Pfaffian polyominos on the Klein bottle, J. Math. Chem., 2018, 56(10): 3147-3160.
[16] Yan W.G., Yeh Y.-N. and Zhang F.J., Dimer problem on the cylinder and torus, Phys. A, 2008, 387(24): 6069-6078.
[17] Zhang L.Z., Wang Y. and Lu F.L., Pfaffian graphs embedding on the torus, Sci. China Math., 2013, 56(9): 1957-1964.
[1] 杨超, 任韩. 关于3-正则图的消圈数和点荫度的一个注记[J]. 数学进展, 2019, 48(4): 504-508.
[2] 刘颖;邵嘉裕;袁西英;. 具有完美匹配树的代数连通度的排序(英文)[J]. 数学进展, 2008, 37(3): 269-282.
[3] 黄元秋,刘彦佩. 关于3-正则图的平均亏格(英文)[J]. 数学进展, 2002, 31(1): 56-64.
Viewed
Full text


Abstract

Cited

  Discussed   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .