北京大学期刊网　|　作者　　审稿人　　编委专家　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展 - 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
/   /   推荐

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

 [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