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).
刘小青,许进. 一种特殊的多米诺扩缩运算[J]. 电子与信息学报, 2017, 39(1): 221-230.
LIU Xiaoqing, XU Jin. Special Type of Domino Extending-contracting Operations. JEIT, 2017, 39(1): 221-230.
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.
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.
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.
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.
