欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
设G是一个k-色图,若G的所有k-着色是Kempe等价的,则称G为Kempe图。表征色数33的Kempe图特征是一尚待解决难题。该文对极大平面图的Kempe等价性进行了研究,其主要贡献是：（1）发现导致两个4-着色是Kempe等价的关键子图为2-色耳,故对2-色耳的特征进行了深入研究;（2）引入σ-特征图,清晰地刻画了一个图中所有4-着色之间的关联关系,并深入研究了σ-特征图的性质;（3）揭示了4-色非Kempe极大平面图的Kempe等价类可分为树型,圈型和循环圈型,并指出这3种类型可同时存在于一个极大平面图的4-着色集中;（4）研究了Kempe极大平面图特征,给出了该类图的多米诺递推构造法,以及两个Kempe极大平面图猜想。
英文摘要：
Let G be a k-chromatic graph. G is called a Kempe graph if all k-colorings of G are Kempe equivalent. It is an unsolved and hard problem to characterize the properties of Kempe graphs with chromatic number ≥3. The Kempe equivalence of maximal planar graphs is addressed in this paper. Our contributions are as follows：（1） Observe and study a class of subgraphs, called 2-chromatic ears, which play a critical role in guaranteeing the Kempe equivalence between two 4-colorings;（2） Introduce and explore the properties of s-characteristic graphs, which clearly characterize the relations of all 4-colorings of a graph;（3） Divide the Kempe equivalent classes of non-Kempe 4-chromatic maximal planar graphs into three classes, tree-type, cycle-type, and circular-cycle-type, and point out that all these three classes can exist simultaneously in the set of 4-colorings of one maximal planar graph;（4） Study the characteristics of Kempe maximal planar graphs, introduce a recursive domino method to construct such graphs, and propose two conjectures.
同期刊论文项目
同项目期刊论文
期刊信息
位置：