Halin圖的無包含邊染色
打開文本圖片集
摘要： 探究給定最大度的Halin圖的無包含邊色數(shù)的上界，通過分析極小反例圖的結(jié)構(gòu)，在給定部分子圖的染色下，對剩余圖進行特殊染色。結(jié)果表明：最大度為Δ的Halin圖的無包含邊色數(shù)不超過Δ+2。
關(guān)鍵詞： Halin圖； 無包含邊染色； 無包含邊色數(shù)； 極小反例圖
中圖分類號： O 157.5文獻標(biāo)志碼： 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 預(yù)備知識
設(shè)G是簡單無向圖，V（G），E（G），Δ（G）和δ（G）分別表示圖G的頂點集、邊集、最大度和最小度，映射φ：E（G）→C={1，2，3，…，k}為圖G的一個正常邊染色，即對任意相鄰邊e1和e2，有φ（e1）≠φ（e2）。（剩余7957字）