一種特殊的多米諾擴縮運算

劉小青; 許進

doi:10.11999/JEIT160886

一種特殊的多米諾擴縮運算

doi: 10.11999/JEIT160886 cstr: 32379.14.JEIT160886

劉小青¹,
許進^1,

基金項目:

國家973計劃項目(2013CB329600)，國家自然科學基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)

計量
- 文章訪問數: 1136
- HTML全文瀏覽量: 130
- 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)

訪問統(tǒng)計