4-正则图着色的Kempe等价性

刘小青; 许进

doi:10.11999/JEIT160716

4-正则图着色的Kempe等价性

doi: 10.11999/JEIT160716

刘小青¹,
许进²

1.
(北京大学信息科学技术学院北京 100871) ②(北京大学高可信软件技术教育部重点实验室北京 100871)

基金项目:

国家973计划项目(2013CB329600)，国家自然科学基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

计量
- 文章访问数: 1543
- HTML全文浏览量: 195
- PDF下载量: 273
- 被引次数: 0
出版历程
- 收稿日期: 2016-07-07
- 修回日期: 2017-02-22
- 刊出日期: 2017-05-19

Kempe Equivalence of Colorings of 4-regular Graphs

LIU Xiaoqing¹,
XU Jin²

1.
(School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China)

Funds:

The National 973 Program of China (2013CB 329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

摘要

摘要: 给定一个图G及它的一个正常顶点着色f, G中任意两种颜色的顶点导出子图称为G的一个2-色导出子图，该2-色导出子图的分支称为G的一个2-色分支。Kempe变换是指将图G的某个2-色分支实施颜色互换。若两个着色之间可通过若干次Kempe变换达到对方，则这两个着色是Kempe等价的。Mohar猜想当k3时，对于任意的连通k-正则图G，若G不是完全图，则G的所有k-着色是Kempe等价的。Feghali等人解决了k=3时的情况，当k4时，此猜想尚未解决。该文研究了k=4时的情况，证明了：(1)若G是一个连通度小于3的4-正则图，则G的所有4-着色是Kempe等价的；(2)若G是4-正则图，且含有与4-轮或近5-阶完全图同构的子图，则G的所有4-着色是Kempe等价的；(3)若G是一个3-连通4-正则图，且G存在一个顶点x和一个4-着色f，满足x的邻域中有3个或4个顶点在f下着相同颜色，则G的所有4-着色是Kempe等价的。
- Kempe等价 /
- Kempe变换 /
- Kempe等价类 /
- 4-正则图
Abstract: Given a graphG and a proper vertex coloring ofG, a 2-coloring induced subgraph ofG is a subgraph induced by all the vertices with one of two colors, a component of a 2-coloring induced subgraph is called a 2-coloring component. To make a Kempe change is to obtain one coloring from another by exchanging the colors of vertices in a 2-coloring component. Two colorings are Kempe equivalent if each one can be obtained from the other by a series of Kempe changes. Mohar conjectured that, for k3, all k-colorings of connected k-regular graphs that are not complete are Kempe equivalent. Feghali et al. addressed the case k=3, and it is still an unsolved conjecture for k4. This paper considers the casek=4 by showing that: (1) ifG is a connected 4-regular graph that is not 3-connected, then all 4-colorings ofG are Kempe equivalent; (2) ifG is a connected 4-regular graph that contains an induced subgraph isomorphic to a 4-wheel or a nearly complete graph of order 5, then all 4-colorings ofG are Kempe equivalent; (3) ifG is a 3-connceted 4-regular graph with a 4-coloringf and a vertexx such that there are three or four neighbors ofx colored with the same color under f, then all 4-colorings ofG are Kempe equivalent.
- Kempe equivalent /
- Kempe change /
- Kempe equivalent class /
- 4-regular graph

HTML全文

参考文献(18)

KEMPE A B. On the geographical problem of the four colors[J]. American Journal of Mathematics, 1879, 2(3): 193-200. doi: 10.2307/2369235.

MUHLENTHALER M and WANKA R. The connectedness of clash-free timetables[C]. 10th International Conference of the Practice and Theory of Automated Timetabling, York, United Kingdom, 2014: 26-29.

WANG J S, SWENDSEN R H, and KOTECKY R. Antiferromagnetic potts models[J]. Physical Review Letters, 1989, 63(2): 109-112. doi: 10.1103/PhysRevLett.63.109.

WANG J S, SWENDSEN R H, and KOTECKY R. Three- state antiferromagnetic potts models: A Monte Carlo study[J]. Physical Review B, 1990, 42(4): 2465-2474. doi: 10.1103/ PhysRevB.42.2465.

VIGODA E. Improved bounds for sampling colorings[J]. Journal of Mathematical Physics, 2000, 41(3): 51-59. doi: 10.1063/1.533196.

FISK S. Geometric coloring theory[J]. Advances in Mathematics, 1977, 24(3): 298-340. doi: 10.1016/0001-8708 (77)90061-5.

MEYNIEL H. Les 5-colorations d'un graphe planaire forment une classe de commutation unique[J]. Journal of Combinatorial Theory Series B, 1978, 24(3): 251-257. doi: 10.1016/0095-8956(78)90042-4.

MOHAR B. Kempe Equivalence of Colorings[M]. Graph Theory in Paris. Birkhuser Basel, 2006: 287-297. doi: 10.1007/978-3-7643-7400-6_22.

VERGNAS M L and MEYNIEL H. Kempe classes and the Hadwiger conjecture[J]. Journal of Combinatorial Theory Series B, 1981, 31(1): 95-104. doi: 10.1016/S0095-8956(81) 80014-7.

BERTSCHI M E. Perfectly contractile graphs[J]. Journal of Combinatorial Theory, Series B, 1990, 50(2): 222-230. doi: 10.1016/0095-8956(90)90077-D.

MEYNIEL H. The graphs whose odd cycles have at least two chords[J]. Annals of Discrete Mathematics, 1984, 88(21): 115-119. doi: 10.1016/S0304-0208(08)72927-X.

FEGHALI C, JOHNSON M, and PAULUSMA D. Kempe cquivalence of colourings of cubic graphs[J]. European Journal of Combinatorics, 2017, 59(2): 1-10. doi: 10.1016/ j.ejc.2016.06.008.

MCDONALD J, MOHAR B, and SCHEIDE D. Kempe equivalence of edge-colorings in subcubic and subquartic graphs[J]. Journal of Graph Theory, 2012, 70(2): 226-239. doi: 10.1002/jgt.20613.

BELCASTRO S M and HAAS R. Counting edge-Kempe- equivalence classes for 3-edge-colored cubic graphs[J]. Discrete Mathematics, 2014, 325(13): 77-84. doi: 10.1016/j. disc.2014.02.014.

许进. 极大平面图的结构与着色理论(2)多米诺构形与扩缩运算[J]. 电子与信息学报, 2016, 38(6): 1271-1327. doi: 10.11999 /JEIT160224.

XU J. Theory on structure and coloring of maximal planar graphs (2) Domino configurations and extending- ccontracting operations[J]. Journal of Electronics Information Technology, 2016, 38(6): 1271-1327. doi: 10. 11999/JEIT160224.

许进. 极大平面图的结构与着色理论(4)-运算与Kempe等价类[J]. 电子与信息学报, 2016, 38(7): 1557-1585. doi: 10. 11999/JEIT160483.

XU J. Theory on structure and coloring of maximal planar graphs (4):-operations and Kempe equivalent classes[J]. Journal of Electronics Information Technology, 2016, 38(7): 1557-1585. doi: 10.11999/JEIT160483.

施引文献

资源附件(0)

访问统计