|
|
|
| Special Type of Domino Extending-contracting Operations |
| LIU Xiaoqing XU Jin |
(School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China)
(Key Laboratory of High Confidence Software Technologies, Peking University, Beijing 100871, China) |
|
|
|
|
Abstract In this paper, a new domino extending-contracting operation, called 334 extending-contracting operation, is put forward, on the basis of which, it is proposed to construct a particular kind of graphs, i.e., 334-type maximal planar graphs, and proved that all those graphs are tree-type and 2-chromatic cycle-unchanged colored and every 334-type maximal planar graphs of order 4k has exactly 2k-1 2-chromatic cycled-unchanged colorings and 2k-2 tree-colorings. Additionally, it is proved that an infinite family of purely tree-colored graphs can be generated by implementing a series of 334 extending-wheel operations, and conjectured that if a maximal planar graph G is purely tree-colored (purely cycle-colored or impure-colored), then the graph obtained by implementing one 334 extending-wheel (contracting-wheel) operation on G is still purely tree-colored (purely cycle-colored or impure-colored).
|
|
Received: 29 August 2016
Published: 14 December 2016
|
|
|
| Fund: The National 973 Program of China (2013CB329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437) |
|
Corresponding Authors:
XU Jin
E-mail: jxu@pku.edu.cn
|
|
|
|
| [1] |
MOHAR B. Kempe Equivalence of Colorings[M]. Graph Theory in Paris. Birkhäuser Basel, 2006: 287-297. doi: 10.1007/978-3-7643-7400-6_22.
|
| [2] |
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.
|
| [3] |
FEGHALI C, JOHNSON M, and PAULUSMA D. Kempe equivalence of colourings of cubic graphs[J]. Electronic Notes in Discrete Mathematics, 2015, 49: 243-249. doi: 10.1016/ j.endm.2015.06.034.
|
| [4] |
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.
|
| [5] |
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.
|
| [6] |
许进. 极大平面图的结构与着色理论(3): 纯树着色与唯一4-色极大平面图猜想[J]. 电子与信息学报, 2016, 38(6): 1328-1353. doi: 10.11999/JEIT160409.
|
|
XU J. Theory on structure and coloring of maximal planar graphs(3): Purely tree-colorable and uniquely 4-colorable maximal planar graph conjectures[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1328-1353. doi: 10.11999/JEIT160409.
|
| [7] |
XU J, LI Z P, and ZHU E Q. On purely tree-colorable planar graphs[J]. Information Processing Letters, 2016, 116(8): 532-536. doi: 10.1016/j.ipl.2016.03.011.
|
| [8] |
GREENWELL D and KRONK H V. Uniquely line-colorable graphs[J]. Canadian Mathematical Bulletin, 1973, 16(4): 525-529. doi: 10.4153/CMB-1973-086-2.
|
| [9] |
THOMASON A G. Hamiltonian cycles and uniquely edge colourable graphs[J]. Annals of Discrete Mathematics, 1978, 3: 259-268. doi:10.1016/S0167-5060(08)70511-9.
|
| [10] |
FIORINI S and WILSON R J. Edge colouring of graphs[J]. Research Notes in Mathematics, 1977, 23(1): 237-239.
|
| [11] |
FISK S. Geometric coloring theory[J]. Advances in Mathematics, 1977, 24(3): 298-340. doi: 10.1016/0001-8708 (77)90061-5.
|
| [12] |
TOMMY R J and BJARNE T. Graph Coloring Problems[M]. New York: USA, John Wiley & Sons, Inc., 1994: 1-295.
|
| [13] |
许进. 极大平面图的结构与着色理论(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.
|
| [14] |
许进. 极大平面图的结构与着色理论(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-contracting operations[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1271-1327. doi: 10.11999/JEIT 160224.
|
| [15] |
BONDY J A and MURTY U S R. Graph Theory[M]. New York: USA, Springer, 2008: 8-200.
|
|
|
|
