2025-11-23T03:01:16.593819

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

Falcón, Venkatachalam, Margaret
Let $G$ and $H$ be two graphs, each one of them being a path, a cycle or a star. In this paper, we determine the $b$-chromatic number of every subdivision-vertex neighbourhood corona $G\boxdot H$ or $G\boxdot K_n$, where $K_n$ is the complete graph of order $n$. It is also established for those graphs $K_n\boxdot G$ having $m$-degree not greater than $n+2$. All the proofs are accompanied by illustrative examples.
academic

Determining the b-chromatic number of subdivision-vertex neighbourhood coronas

基本信息

  • 论文ID: 2302.13667
  • 标题: Determining the b-chromatic number of subdivision-vertex neighbourhood coronas
  • 作者: Raúl M. Falcón (Universidad de Sevilla, Spain), M. Venkatachalam, S. Julie Margaret (Kongunadu Arts and Science College, India)
  • 分类: math.CO (Combinatorics)
  • 发表时间: 2023年2月27日
  • 论文链接: https://arxiv.org/abs/2302.13667

摘要

设GG和HH为两个图，每个都是路径、循环或星图。本文确定了每个细分顶点邻域冠图G⊡HG\boxdot H或G⊡KnG\boxdot K_n的bb-色数，其中KnK_n是nn阶完全图。对于mm-度不大于n+2n+2的图Kn⊡GK_n\boxdot G也建立了相应结果。所有证明都配有说明性例子。

研究背景与动机

问题背景

  1. b-色数概念：Irving和Manlove在1999年引入了图的b-色染色概念，这是一种特殊的正常kk-染色，要求每种颜色都有一个b-顶点（该顶点与所有其他颜色的顶点都相邻）。
  2. 计算复杂性：确定图的b-色数在一般情况下是NP-困难问题，但对树而言是多项式时间可解的。
  3. 图积研究：已有大量研究关注各种图积的b-色数，如笛卡尔积、直积、强积、字典序积等。

研究动机

  1. 理论完善：细分顶点邻域冠图（SVN corona）是一种重要的图构造方法，但其b-色数研究相对缺乏。
  2. 方法系统化：需要系统性地研究基础图类（路径、循环、星图、完全图）的SVN冠图的b-色数。
  3. 应用价值：b-色数在网络着色、频率分配等实际问题中具有重要应用。

核心贡献

  1. 完全确定了基础图类的SVN冠图b-色数：对于路径PnP_n、循环CnC_n、星图SnS_n与路径、循环、星图、完全图的SVN冠图，给出了精确的b-色数公式。
  2. 建立了完全图SVN冠图的部分结果：对于mm-度不超过n+2n+2的Kn⊡GK_n\boxdot G，确定了其b-色数。
  3. 提供了构造性证明方法：所有结果都通过构造具体的最优b-色染色来证明，并配有详细的图示例子。
  4. 发展了系统性分析框架：建立了分析SVN冠图b-色数的一般方法和技术工具。

方法详解

任务定义

输入：两个图GG和HH，其中G,H∈{Pn,Cn,Sn,Kn}G,H \in \{P_n, C_n, S_n, K_n\}输出：SVN冠图G⊡HG\boxdot H的b-色数φ(G⊡H)\varphi(G\boxdot H)约束：对于Kn⊡GK_n\boxdot G的情况，要求m(Kn⊡G)≤n+2m(K_n\boxdot G) \leq n+2

SVN冠图构造

给定图GG和HH，SVN冠图G⊡HG\boxdot H的构造过程：

  1. 从图GG的细分图S(G)S(G)开始（在每条边上插入一个新顶点）
  2. 添加∣V(G)∣|V(G)|个HH的顶点不相交副本
  3. 将S(G)S(G)中每个原顶点uiu_i的邻域中的所有顶点连接到第(i+1)(i+1)个HH副本的所有顶点

关键技术工具

1. m-度概念

对于nn阶图GG，其mm-度定义为： m(G):=∣{i∈{1,…,n}:d(vi−1)≥i−1}∣m(G) := |\{i \in \{1,\ldots,n\} : d(v_{i-1}) \geq i-1\}| 其中顶点按度数非递增排序。

2. 基本界限

  • 下界：χ(G)≤φ(G)\chi(G) \leq \varphi(G)（色数不超过b-色数）
  • 上界：φ(G)≤Δ(G)+1\varphi(G) \leq \Delta(G) + 1（b-色数不超过最大度加1）
  • m-度界限：φ(G)≤m(G)\varphi(G) \leq m(G)

3. SVN冠图的度数公式

对于G⊡HG\boxdot H中的顶点vv：

d_G(v), & \text{if } v \in V(G) \\ 2|V(H)| + 2, & \text{if } v \in I(G) \\ d_G(u_i) + d_H(v_j), & \text{if } v = v_{i,j} \end{cases}$$ ### 分析策略 论文采用分类讨论的方法，针对不同的图类组合： 1. **路径的SVN冠图**（第3节） 2. **循环的SVN冠图**（第4节） 3. **星图的SVN冠图**（第5节） 4. **完全图的SVN冠图**（第6节） 每种情况都通过构造具体的b-色染色来证明上界的紧性。 ## 主要结果 ### 路径SVN冠图的b-色数 **定理6**（$P_n \boxdot P_t$）： $$\varphi(P_n \boxdot P_t) = \begin{cases} 4, & \text{if } n=3 \text{ and } t \in \{3,4\} \\ 5, & \text{if } (n=3 \text{ and } t \geq 5) \text{ or } n \in \{4,5\} \\ n-1, & \text{if } 6 \leq n \leq 2t+3 \\ 2t+3, & \text{otherwise} \end{cases}$$ **定理7-9**：类似地给出了$P_n \boxdot C_t$、$P_n \boxdot S_t$、$P_n \boxdot K_t$的精确公式。 ### 循环SVN冠图的b-色数 **定理11**（$C_n \boxdot P_t$）： $$\varphi(C_n \boxdot P_t) = \begin{cases} 5, & \text{if } n \in \{3,4\} \\ n, & \text{if } 5 \leq n \leq 2t+2 \\ 2t+3, & \text{otherwise} \end{cases}$$ ### 星图SVN冠图的b-色数 **定理17**：对于星图与基础图类的SVN冠图，建立了完整的b-色数公式，其中关键结果包括： $$\varphi(S_n \boxdot K_{t'}) = \min\{n, t'+2\} + t'$$ ### 完全图SVN冠图的b-色数 **定理20-24**：在$m$-度约束下，给出了$K_n \boxdot G$的b-色数，例如： $$\varphi(K_n \boxdot P_t) = \begin{cases} n+1, & \text{certain conditions} \\ n+2, & \text{other conditions} \end{cases}$$ ## 技术创新点 ### 1. 构造性证明方法 - 不仅证明了上界，还通过显式构造最优b-色染色证明了下界 - 每个构造都配有详细的图示例子，增强了结果的可验证性 ### 2. b-彩虹集概念 引入了b-彩虹集的概念来简化b-顶点的识别，在图中用不同符号标记： - 叉号×：特定b-彩虹集的顶点 - 三角形△：其他b-顶点 - 圆圈●：普通顶点 ### 3. 模运算技巧 在染色构造中大量使用模运算来确保染色的周期性和正确性，例如： $$c(u_i) = (i+1) \bmod \min\{m(P_n \boxdot P_t), n\}$$ ### 4. 分类讨论的系统化 根据参数范围进行精细的分类讨论，确保覆盖所有可能情况。 ## 实验验证 ### 图示验证 论文提供了大量的图示例子来验证理论结果： - 图2：$P_{10} \boxdot P_3$的最优b-色染色 - 图3-4：不同参数下路径SVN冠图的染色 - 图11：循环SVN冠图的染色示例 - 图17-18：星图SVN冠图的染色构造 ### 构造验证 每个定理的证明都包含了具体的染色构造算法，可以直接验证： 1. 染色的正确性（相邻顶点不同色） 2. b-顶点的存在性（每种颜色都有b-顶点） 3. 最优性（达到理论上界） ## 相关工作 ### b-色数研究历史 1. **Irving-Manlove (1999)**：首次引入b-色数概念 2. **各种图积的研究**：笛卡尔积、直积、强积等的b-色数已有广泛研究 3. **特殊图类**：路径、循环、星图、完全图的b-色数已知 ### 本文的位置 - **填补空白**：SVN冠图的b-色数研究相对缺乏 - **方法创新**：提供了系统性的构造方法 - **结果完整**：给出了基础图类组合的完整结果 ## 结论与讨论 ### 主要结论 1. **完整性**：对于基础图类（路径、循环、星图、完全图）的SVN冠图，给出了完整的b-色数确定结果 2. **精确性**：所有结果都是精确值，不是近似或界限 3. **构造性**：提供了具体的最优染色构造方法 ### 局限性 1. **图类限制**：仅考虑了基础图类，对一般图的结果有待进一步研究 2. **完全图约束**：对$K_n \boxdot G$的结果需要$m$-度约束条件 3. **复杂度**：某些情况下的分类讨论较为复杂 ### 未来方向 1. **扩展图类**：研究更一般图类的SVN冠图b-色数 2. **算法研究**：开发高效的b-色数计算算法 3. **应用探索**：将结果应用到实际的网络着色问题中 ## 深度评价 ### 优点 1. **理论贡献显著**：系统性地解决了一类重要图积的b-色数问题 2. **方法严谨**：构造性证明方法确保了结果的可靠性 3. **表述清晰**：大量图示和例子使得复杂的证明易于理解 4. **结果完整**：覆盖了基础图类的所有重要组合 ### 不足 1. **技术创新有限**：主要是现有方法的系统化应用，缺乏根本性的新技术 2. **应用价值不明确**：缺乏对实际应用场景的讨论 3. **计算复杂度分析缺失**：未讨论构造算法的时间复杂度 ### 影响力 1. **理论价值**：为图的b-色数理论提供了重要补充 2. **方法价值**：构造方法可以推广到其他图积的研究 3. **完整性价值**：填补了SVN冠图b-色数研究的空白 ### 适用场景 1. **理论研究**：图论和组合优化领域的基础研究 2. **网络设计**：需要考虑邻域约束的网络着色问题 3. **算法设计**：作为更复杂图着色算法的基础模块 ## 参考文献 论文引用了25篇相关文献，主要包括： - Irving & Manlove (1999): b-色数的原始定义 - Kouider & Mahéo等: 各种图积的b-色数研究 - Liu & Lu (2013): SVN冠图的谱理论研究 - Brooks (1941): 图着色的经典结果