Special Type of Domino Extending-contracting Operations

LIU Xiaoqing; XU Jin

doi:10.11999/JEIT160886

Volume 39 Issue 1

Jan. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2017 > 39(1): 221-230

LIU Xiaoqing, XU Jin. Special Type of Domino Extending-contracting Operations[J]. Journal of Electronics & Information Technology, 2017, 39(1): 221-230. doi: 10.11999/JEIT160886

Citation:

LIU Xiaoqing, XU Jin. Special Type of Domino Extending-contracting Operations[J]. Journal of Electronics & Information Technology, 2017, 39(1): 221-230. doi: 10.11999/JEIT160886

LIU Xiaoqing, XU Jin. Special Type of Domino Extending-contracting Operations[J]. Journal of Electronics & Information Technology, 2017, 39(1): 221-230. doi: 10.11999/JEIT160886

Citation:

LIU Xiaoqing, XU Jin. Special Type of Domino Extending-contracting Operations[J]. Journal of Electronics & Information Technology, 2017, 39(1): 221-230. doi: 10.11999/JEIT160886

PDF( 448 KB)

Special Type of Domino Extending-contracting Operations

doi: 10.11999/JEIT160886

LIU Xiaoqing¹,
XU Jin^1
,

Funds:

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

Received Date: 2016-08-29
Rev Recd Date: 2016-12-06
Publish Date: 2017-01-19

Abstract

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 order4k has exactly2k-1 2-chromatic cycled-unchanged colorings and2k-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 Gis 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).
- Semi-funnels,
- Tree-type and 2-chromatic cycle-unchanged colored,
- Purely tree-colored,
- 334 extending- wheel operations

FullText(HTML)

References(18)

References

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.

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.

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.

许进. 极大平面图的结构与着色理论(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.

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.

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.

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.

FIORINI S and WILSON R J. Edge colouring of graphs[J]. Research Notes in Mathematics, 1977, 23(1): 237-239.

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

TOMMY R J and BJARNE T. Graph Coloring Problems[M]. New York: USA, John Wiley Sons, Inc., 1994: 1-295.

许进. 极大平面图的结构与着色理论(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.

许进. 极大平面图的结构与着色理论(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.

BONDY J A and MURTY U S R. Graph Theory[M]. New York: USA, Springer, 2008: 8-200.

Relative Articles

Supplements(0)

Cited By

Proportional views