Halin圖的無包含邊染色

打開文本圖片集

摘要： 探究給定最大度的Halin圖的無包含邊色數(shù)的上界，通過分析極小反例圖的結(jié)構(gòu)，在給定部分子圖的染色下，對(duì)剩余圖進(jìn)行特殊染色。結(jié)果表明：最大度為Δ的Halin圖的無包含邊色數(shù)不超過Δ+2。

關(guān)鍵詞： Halin圖； 無包含邊染色； 無包含邊色數(shù)； 極小反例圖

中圖分類號(hào)： O 157.5文獻(xiàn)標(biāo)志碼： A   文章編號(hào)： 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 預(yù)備知識(shí)

設(shè)G是簡(jiǎn)單無向圖，V（G），E（G），Δ（G）和δ（G）分別表示圖G的頂點(diǎn)集、邊集、最大度和最小度，映射φ：E（G）→C={1，2，3，…，k}為圖G的一個(gè)正常邊染色，即對(duì)任意相鄰邊e1和e2，有φ（e1）≠φ（e2）。（剩余7957字）