图的顶点色数与调和指标的若干界

《Discrete Mathematics》：Some bounds for the vertex chromatic number and harmonic index of a graph

　　

设G是一个阶为n、规模为m的图。若G是阶至少为5的连通图，我们证明χ(G)≤?m/n?。此外，我们证明若G的围长大于2k+1，则χ(G)≤?(k+2)√((k+2)m)?+1。已有结果证明：对每个无孤立顶点的图G，χ(G)≤2H(G)，其中H(G)=∑_{uv∈E(G)}2/(d(u)+d(v))。我们改进这一结果并以更短的证明表明col(G)≤2H(G)，其中col(G)=max{δ(H)+1:H?G}。本文还证明：若G是阶至少3且无孤立顶点的无三角形图，则χ(G)≤?H(G)?。

图的顶点色数与调和指标的若干界：一项基于度结构与围长条件的理论研究

**研究背景与问题**

图论中，图的着色问题是核心研究方向之一，其基本目标是以最少的颜色数对图的顶点进行染色，使得任意相邻顶点颜色不同，该最少颜色数称为图的色数，记为χ(G)。色数的精确计算在一般情形下是NP-困难的，因此寻求色数的有效上界具有重要理论价值。多年来，研究者致力于利用图的各种结构参数——如阶数、规模、最小度、最大度、围长以及各类拓扑指数——来估计色数的上界。

在化学图论领域，Randi?指数R(G)由Milan Randi?于1975年提出，定义为R(G)=∑_{uv∈E(G)}1/√(d(u)d(v))，其中d(u)表示顶点u的度。该指数在数学化学中具有广泛应用。调和指标H(G)定义为H(G)=∑_{uv∈E(G)}2/(d(u)+d(v))。由AM-GM不等式可知H(G)≤R(G)，且等号成立当且仅当G的每个连通分量都是正则图。Hansen和Vukicevi?建立了Randi?指数与色数之间的关系。已有文献证明，对任意无孤立顶点的图G，χ(G)≤2H(G)。然而，这一上界对于无三角形图是否能够改进，以及是否存在更精确的基于阶数和规模的色数上界，仍是值得探讨的问题。

本文针对上述问题开展了系统研究。研究的动机包括三个方面：其一，探索连通图的色数关于阶数n和规模m的简洁上界；其二，在围长条件约束下建立更一般的色数上界；其三，利用调和指标改进无三角形图的色数估计，并推广已有的2H(G)上界至着色数col(G)。

**研究内容与主要结果**

研究人员首先证明了对于阶至少5的连通(m,n)-图G，χ(G)≤?m/n?。这一结果通过分情况讨论完成证明：当m≤2n-2时，利用最小度顶点删除技巧与归纳法；当m≥2n-1时，借助已有定理并结合函数单调性分析。研究人员还提出一个猜想式问题：对连通无三角形图G，是否成立χ(G)≤?m/(2√n)?+1，并通过计算机搜索验证了阶数不超过9的所有连通无三角形图均满足该猜想。

其次，研究人员证明了若图G的围长满足g(G)>2k+1，其中k为非负整数，则χ(G)≤?(k+2)√((k+2)m)?+1。该定理的证明采用对规模m的归纳法，结合围长条件导出的距离分层结构分析，利用BFS分层中第k层顶点数量增长的下界来估计跨层边数，进而完成归纳步骤。

再次，针对无三角形图，研究人员证明了：若G是阶n≥3且最小度δ≥1的无三角形图，则χ(G)≤?H(G)?。这是对已有上界χ(G)≤2H(G)在无三角形图类上的实质性改进。证明分为三种情形：当δ≤χ(G)-2时，通过删除最小度顶点并利用归纳法；当χ(G)-1≤δ
最后，研究人员将已有结果χ(G)≤2H(G)推广为更强的结论：对任意无孤立顶点的图G，col(G)≤2H(G)，其中col(G)为着色数，定义为所有子图最小度加1的最大值。由于χ(G)≤col(G)，该结果蕴含了χ(G)≤2H(G)，且证明更短。该定理的证明通过对阶数n归纳：若δ=col(G)-1，直接利用边数与最大度的关系；若δ
**技术方法概述**

本文主要采用以下关键技术方法：（1）最小度顶点删除法与归纳法结合，通过删除图的最小度顶点，利用归纳假设对剩余图着色，再将删除顶点加入；（2）围长条件下的BFS分层结构分析，利用距离分层中顶点数量的指数增长下界来估计边数约束；（3）图论中经典定理的引用与推广，包括Wilf定理、Mantel定理以及关于Randi?指标删除边后变化的引理；（4）函数单调性分析与不等式技巧，用于证明复杂上界关系；（5）SageMath计算机辅助验证，用于检查小阶数图上的猜想。文中无需样本队列来源说明。

**研究结果详述**

研究人员依次建立了以下主要定理：

**定理1** 设G是阶至少5的连通(m,n)-图，则χ(G)≤?m/n?。证明中，当χ(G)≤4且?m/n?≥4时结论显然；否则通过SageMath验证所有不超过9个顶点的图成立。对于χ(G)≥5且n≥10的情形，分m≤2n-2和m≥2n-1两种情况处理。第一种情况利用最小度顶点删除和连通化操作，结合一个关于连通并图染色数的引理；第二种情况引用文献中的色数上界并通过函数单调性完成证明。

**定理4** 设G是围长g(G)>2k+1的(m,n)-图，k为非负整数，则χ(G)≤?(k+2)√((k+2)m)?+1。k=0时由Wilf定理直接得到χ(G)≤√(2m)+1。一般情形通过对m归纳，利用围长条件保证BFS分层中Γ_k(v)内的顶点互不相邻，且|Γ_k(v)|≥δ(δ-1)^{k-1}，从而估计跨层边数并完成归纳。

**定理6** 若G是阶n≥3且最小度δ≥1的无三角形图，则χ(G)≤?H(G)?。三种情形分别采用归纳法、调和指标下界定理和Mantel定理完成证明。推论进一步得到χ(G)≤?R(G)?。

**定理13** 设G是无孤立顶点的图，则col(G)≤2H(G)，等号成立当且仅当G是完全图与若干孤立顶点的并。证明通过对n归纳完成，关键步骤包括边数的下界估计以及调和指标在删除最小度顶点后严格递减的引理。

**讨论与结论**

在讨论部分，研究人员提出了一个开放性问题：对连通无三角形图是否成立χ(G)≤?m/(2√n)?+1，并通过计算机搜索对阶数不超过9的所有连通无三角形图给出了肯定验证。这表明该猜想可能具有更广泛的适用性。

本文的结论可概括为：第一，建立了连通图的色数关于阶数和规模的简洁上界χ(G)≤?m/n?；第二，在围长大于2k+1的条件下得到了形式统一的色数上界χ(G)≤?(k+2)√((k+2)m)?+1，该结果将k=0情形的已有结论推广至任意非负整数k；第三，对无三角形图将调和指标上界从2H(G)改进为?H(G)?；第四，将χ(G)≤2H(G)强化为col(G)≤2H(G)，获得了更一般的着色数上界。这些结果丰富了色数与度结构参数及拓扑指数之间关系的理论体系，为图着色问题的进一步研究提供了新的工具和思路。