Halin图的无包含边染色

打开文本图片集

摘要： 探究给定最大度的Halin图的无包含边色数的上界，通过分析极小反例图的结构，在给定部分子图的染色下，对剩余图进行特殊染色。结果表明：最大度为Δ的Halin图的无包含边色数不超过Δ+2。

关键词： Halin图； 无包含边染色； 无包含边色数； 极小反例图

中图分类号： O 157.5文献标志码： A   文章编号： 1000-5013（2024）06-0812-04

Inclusion-Free Edge Coloring of Halin Graph

PENG Yan， TAN Yi， CHEN Lili

（School of Mathematical Sciences， Huaqiao University， Quanzhou 362021， China）

Abstract： The upper bound of the inclusion-free chromatic index of Halin graph with the given maximum degree is explored. By analyzing the structure of the minimal counterexample graph， the special coloring to the remaining graph is done under the coloring of the given partial subgraphs. The results show that the inclusion-free chromatic index of Halin graph with the maximum degree Δ is  are not more than Δ+2.

Keywords： Halin graph； inclusion-free edge coloring； inclusion-free chromatic index； minimal counterexample graph

1 预备知识

设G是简单无向图，V（G），E（G），Δ（G）和δ（G）分别表示图G的顶点集、边集、最大度和最小度，映射φ：E（G）→C={1，2，3，…，k}为图G的一个正常边染色，即对任意相邻边e1和e2，有φ（e1）≠φ（e2）。（剩余7957字）