一种特殊的多米诺扩缩运算

刘小青; 许进

doi:10.11999/JEIT160886

一种特殊的多米诺扩缩运算

doi: 10.11999/JEIT160886

刘小青¹,
许进^1,

基金项目:

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

计量
- 文章访问数: 1102
- HTML全文浏览量: 119
- PDF下载量: 329
- 被引次数: 0
出版历程
- 收稿日期: 2016-08-29
- 修回日期: 2016-12-06
- 刊出日期: 2017-01-19

Special Type of Domino Extending-contracting Operations

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)

摘要

摘要: 该文提出一种称为334扩缩运算的多米诺扩缩运算。使用该运算构造了一类特殊的极大平面图334-型极大平面图，证明了该类图均为树型2-色不变圈着色，且每个4k -阶334-型极大平面图恰有2k-1个2-色不变圈着色及2k-2个树着色。证明了该运算可用于构造纯树着色极大平面图，并提出猜想：若极大平面图G是纯树(纯圈，混合)着色，则对G实施334扩(缩)轮运算后，所得之图仍是纯树(纯圈，混合)着色。
- 半封漏斗 /
- 树型2-色不变圈着色 /
- 纯树着色 /
- 334扩轮运算
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

HTML全文

参考文献(18)

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.

施引文献

资源附件(0)

访问统计