在图的笛卡尔积（Corona Product）中的无环图着色分析

《NATIONAL ACADEMY SCIENCE LETTERS-INDIA》：Acyclic Graph Coloring Analysis in the Corona Product of Graphs

本文研究图G与H的冠乘积G°H的递归色数χ?(G°H)，通过分析三种不同情况下的颜色类，结合G和H的递归色数与最大度数，证明当满足递归边色猜想时，G°H的最大度数Δ(G°H)等于其递归色数χ?(G°H)。

　　

摘要

无环图着色问题在网络设计、图算法和组合优化中具有应用价值。给定两个简单、连通且无向的图 G 和 H，它们的冠积 \(G {\circ } H\) 可以将 G 和 H 的结构结合起来，同时在它们的顶点集 V(G) 和 V(H) 之间引入额外的连接。在这项研究中，通过考虑三种不同情况下 V(G) 和 V(H) 的颜色类，分析了 G 和 H 的无环着色参数 \(\chi _{a}(G)\) 和 \(\chi _{a}(H)\)，以确定 \(G {\circ } H\) 的无环着色方案 \( \chi _{a}(G {\circ } H)\)。该研究还基于 \(\chi _{a}(G)\) 和 \(\chi _{a}(H)\) 分析了 \( \chi _{a}(G {\circ } H)\) 和 \( \chi _{a}(H {\circ } G)\)。研究证明了一个重要结果：当 G 和 H 满足无环边着色猜想时，\(G {\circ } H\) 的最大度为 \(\Delta (G {\circ } H) = \chi '_{a}(G {\circ } H)\)，即 \(G {\circ } H\) 的无环色指数。