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

Special Type of Domino Extending-contracting Operations

作　　者：刘小青[1] 许进[2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]北京大学高可信软件技术教育部重点实验室,北京100871

出　　处：《电子与信息学报》2017年第1期221-230,共10页Journal of Electronics & Information Technology

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

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

关 键 词：半封漏斗 树型2-色不变圈着色 纯树着色 334扩轮运算 

分 类 号：O157.5[理学—数学]