本文仅考虑简单有限的无向图. 用$ G=(V, E) $表示顶点集是$ V $, 边集为$ E $的简单有限图. $ G $的阶表示为$ \vert G\vert $, 是指$ G $中顶点的个数. 顶点$ v $的度表示为$ d_G(v) $, 是指$ G $中与顶点$ v $相关联的边数. $ \Delta(G) $表示图$ G $的最大度. 用$ P_n $表示阶为$ n $的路. 图$ G $的一条路$ P_{k+1}=v_0v_1\cdots v_k $, 如果$ P_{k+1} $中的每两个连续的顶点在$ G $中相邻, 且$ d(v_0)\geq 3 $, $ d(v_i)=2(i=1, \cdots, k-1) $, $ d(v_k)=1 $, 则称$ S=v_1\cdots v_k $为图$ G $的悬挂路. 图$ G $的点着色是函数$ C : V $ → $ \mathbb{Z}^+ $. 图中一条路的点着色中如果有一种颜色只使用一次, 我们称这条路为无矛盾的. 如果任意两点间都存在一条无矛盾点着色的路, 我们称这个着色为无矛盾点连通的. 图的无矛盾点连通数表示为$ vcfc(G) $, 是指使$ G $为无矛盾点连通所需的最小颜色数. 显然, 对于所有阶为$ n(n\geqslant 2) $的连通图$ G $, $ vcfc(G)\geqslant 2 $. 在本文中未提到的一些基本定义可见参考文献[1].

树$ T $是任意两个顶点间有且仅有一条路的图, 度为1的点称为叶子, 记为$ leaf(T) $. 记$ \mathcal{T}_{n, k}=\{T $是一个树$ | $$ \vert T\vert=n $且有$ k $个叶子$ \}$; 记$ \mathcal{T}_{n}^{\Lambda} $=$\{ T $是一个树$ | $$ \vert T\vert=n $且$ \Delta(T)=\Lambda(\Lambda \geq 3) \}$. 若将树$ T $中的每个点的各子树看成是从左到右有次序的, 不能互换的, 则称该树$ T $为有序树. 树$ T $中的任意一个顶点都选为树的根, 指定了根的树称为根树. 点的层次从根开始定义起, 根为第一层, 与根相邻的顶点为第二层, 与第二层相邻的顶点(除去第一层)为第三层, 以此类推与第$ i-1 $层相邻的顶点(除去第$ i-2 $层)为第$ i $层, 树中点的最大层次的最小值称为树的高度. 树中点的子树的个数都不大于$ \Lambda $的有序树称为$ \Lambda $叉树. 设$ \Lambda $叉树的高度为$ d $, 除第$ d $层外, 其它各层($ 1\sim d-1 $)的点数都达到最大个数, 第$ d $层有叶子, 并且叶子都是从左到右依次排布, 则称为完全$ \Lambda $叉树. 特别地, 记$ \Lambda_d= $$\{ T $是一个完全$ \Lambda $叉树$ |\vert T\vert=\Lambda^d-1 $且高度为$ d \}$. 记$ V_1=\{v| $高度为$ d $的树$ T $第1层至第$ d-1 $层的点$ \}$, $ V_2=\{v| $高度为$ d $的树$ T $第$ d $层的点$ \}$, $ \mathcal{T}_{\Lambda}=\{T $是一个树$ |d_T(v)=\Lambda, v\in V_1 $且$ d_T(v)=1, v\in V_2 \}$. 树$ T $中如果存在点$ x $使得$ G-x $的任意连通分支至多包含$ \frac{\vert V(G)-x\vert}{2} $个点, 则称点$ x $为平衡点^[2]. 树$ T $的深度记为$ d_V(T) $, 表示如下算法中的迭代次数: 树$ T $中顶点$ v $的深度表示为$ d_V(v) $, 是指顶点$ v $在迭代过程中被删去的排序数. 即如果顶点$ v $在第$ d $-次迭代中被删除, 那么$ v $具有深度$ d $^[2]. 在文献[2]中给出了算法:

算法1树的无矛盾点连通算法

输入: 一个顶点为$ n $的树$ T $. 输出: 树$ T $的无矛盾点着色$ c $ : $ V(T)\rightarrow \{1, 2, \cdots, k\} $. 步骤1:令$ F=T $, $ c $ : $ V \rightarrow \{0\} $. 步骤2:判断$ F $中是否存在顶点数大于等于2的分支. 如果有, 回到步骤3; 如果没有, 回到步骤4. 步骤3:挑选所有顶点数大于等于2的连通分支, 并且删去这些分支的平衡点$ v $, 得到新的连通分支构成的森林$ F' $. 用$ F' $代替F, 更新$ c $ : 对点$ v $赋予$ d_V(v) $. 返回步骤2. 步骤4:返回$ c $.

图的着色问题一直是图论中的热点问题. 李学良等^[4-7]提出了图的无矛盾点连通, 并且对图的无矛盾点连通数做了深入的研究, 对于超图、线图及二连通图等得到了较好的结果. 对于所有的阶为$ n(n\geq 2) $的$ 2- $连通图$ G $都有$ vcfc(G)\geq 2 $, 本文将讨论$ \mathcal{T}_{n, k} $和$ \mathcal{T}_{n}^{\Lambda} $关于无矛盾点连通数的上界和下界. 在讨论$ \mathcal{T}_{n}^{\Lambda} $关于无矛盾点连通数的下界时, 提出了$ \Lambda_d $和$ \mathcal{T}_{\Lambda} $, 并讨论了它们关于无矛盾点连通数的上界.

在文献[8]中, H Chang等提出了平衡边的概念, 且证明了有$ n $个点的路$ P_n $关于边的深度为$ \lceil {\rm{log}}_2n\rceil $. 本文对于有$ n $个点的路$ P_n $给出了如下引理:

引理1  设$ P_n $是阶为$ n(n\geq 2) $的路, 则$ d_V(P_n)=\lceil {\rm{log}}_2(n+1)\rceil $.

证 先证$ d_V(P_n)\geq \lceil {\rm{log}}_2(n+1)\rceil $. 由上述算法可知, 在$ P_n $中深度为$ 1 $的点有$ 1 $个, 深度为$ 2 $的点有$ 2 $个, 深度为$ 3 $的点有$ 4 $个, 以此类推深度为$ i(1\le i \le d_V(P_n)-1) $的点有$ 2^{i-1} $个, 而深度为$ d_V(P_n) $的点至多有$ 2^{d_V(P_n)-1} $个, 从而$ 2^0+2^1+\cdots +2^{d_V(P_n)-1}\geq n $, $ d_V(P_n)\geq \lceil {\rm{log}}_2(n+1)\rceil $.

下证$ d_V(P_n)\le \lceil {\rm{log}}_2(n+1) \rceil $. 我们对$ n $进行数学归纳, 对于$ n=1 $和$ n=2 $显然成立. 选择$ P_n $的中心点并用颜色1对它进行着色, 则剩下的路$ P_1 $和$ P_2 $分别有至多$ \lceil \frac{n-1}{2}\rceil $个点. 由归纳可知, $ {\rm{max}}\{d_V(P_1), d_V(P_2)\}\le \lceil {\rm{log}}_2(\lceil \frac{n-1}{2}\rceil +1)\rceil=\lceil {\rm{log}}_2\lceil\frac{n+1}{2}\rceil \rceil $. 因此, $ d_V(P_n)\le 1+{\rm{max}}\{d_V(P_1), d_V(P_2)\}\le 1+\lceil {\rm{log}}_2\lceil\frac{n+1}{2}\rceil \rceil=\lceil {\rm{log}}_2(n+1) \rceil $, 证毕.

引理2 ^[4]   设$ P_n $是阶为$ n(n\geq 2) $的路, 则$ vcfc(P_n)=\lceil {\rm{log}}_2(n+1) \rceil $.

由引理1和引理2可知$ vcfc(P_n)=d_V(P_n) $, 那么可以得到一种对路的着色方法, 称为中心点着色法, 即点$ v $着颜色$ d_V(v) $.

引理3 ^[9]   设$ T $是阶为$ n(n\geq 2) $的树, 则$ vcfc(T)\le vcfc(P_n) $.

设$ G' $是$ G $的子图, 显然$ G $的无矛盾点连通着色一定是$ G' $的无矛盾点连通着色, 则可以得到以下引理:

引理4  设$ G' $是$ G $的子图, 则$ vcfc(G)\geq vcfc(G') $. 特别地, 设$ T $是阶为$ n(n\geq 2) $的树, 其中$ P $是$ T $的最长路, 则$ vcfc(T)\geq vcfc(P) $.

定理1  设$ T\in \mathcal{T}_{n, k} $, 其中$ n-1=lk+s(0\le s\le k-1) $, 那么

$ vcfc(T)\geq\left\{ \begin{array}{rcl} \lceil log_2(2l+2)\rceil& &{s=0}\\ \lceil log_2(2l+3)\rceil& &{s=1}\\ \lceil log_2(2l+4)\rceil& &{s\geq 2} \end{array} \right.. $

证 因为$ T\in \mathcal{T}_{n, k} $, 则$ T $中含有$ k $个悬挂路. 删除$ T $中最短的悬挂路$ S_1 $得到$ T_1 $; 删除$ T_1 $中的最短悬挂路$ S_2 $得到$ T_2 $; $ \cdots $; 删除$ T_{k-3} $中的最短悬挂路$ S_{k-2} $得到$ T_{k-2} $. 显然$ T_{k-2} $是$ T $中的一条路, 记为$ P $. 下面证明$ P $是$ T $中的最长路. 对$ k $进行归纳, 当$ k=2 $时, $ T_{n, 2} $是一条路, 显然成立. 假设当$ k=m $成立, 即通过上述方法能找到最长路. 下面证明对$ k=m+1 $也成立. 令$ T'\in \mathcal{T}_{n, k} $, $ k=m+1 $且最长路为$ P' $, 删除$ T' $的最短悬挂路$ S'_1 $得到$ T'_1 $, 此时$ T'_1 $是有$ m $个叶子的树, 由归纳可知$ T'_1 $有最长路$ P'' $. 如果$ \vert P'\vert=\vert P''\vert $, 则结果成立. 假设$ \vert P'\vert > \vert P''\vert $, 则$ S'_1\subset P' $. 由于$ S'_1 $是$ T'_1 $的最短悬挂路, 那么与$ S'_1 $关联的点$ v $一定关联另一条悬挂路$ S'_2 $且$ \vert S'_1\vert\le \vert S'_2\vert $. 当$ \vert S'_2\vert\ =\vert S'_1\vert $时, 那么$ T'_1 $存在一条路$ P'-S'_1+S'_2 $有$ \vert P'-S'_1+S'_2\vert=\vert P'\vert\ > \vert P''\vert $, 与$ P'' $是$ T'_1 $的最长路矛盾. 因此$ \vert S'_2\vert\ > \vert S'_1\vert $, 那么可以找到$ T' $的一条路$ P'-S'_1+S'_2 $有$ \vert P'-S'_1+S'_2\vert > \vert P'\vert $, 与$ P' $是$ T' $的最长路矛盾.

从上面的叙述中可以得到以下结论:

$ \begin{align} \vert S_1\vert \le \vert S_2\vert\le \cdots\le \vert S_{k-2} \vert \le \vert P\vert, \end{align} $

(1)

$ \begin{align} \vert S_1\vert +\vert S_2\vert +\cdots +\vert S_{k-2} \vert +\vert P\vert=n , \end{align} $

(2)

$ \begin{align} \vert P\vert \geq 2\vert S_{k-2}\vert +1. \end{align} $

(3)

由(2)可得:

$ \begin{align} \vert P\vert=n-\vert S_1\vert -\vert S_2\vert-\cdots-\vert S_{k-2} \vert\geq n-(k-2)\vert S_{k-2}\vert \end{align} $

(4)

由(3)可得:

$ \begin{align} \vert S_{k-2}\vert\le \frac{\vert P\vert-1}{2}. \end{align} $

(5)

由(4)和(5)可得:

$ \vert P\vert \geq n-\frac{(k-2)(\vert P\vert-1)}{2} $

即

$ \vert P\vert \geq 2\lceil \frac{n-1}{k}\rceil+1. $

下面分三种情况来讨论:

若$ s=0 $, 由上面的叙述可知: 当$ \vert S_1\vert = \vert S_2\vert= \cdots= \vert S_{k-2}\vert=l $时, $ P $是这类树$ T $的最长路中最短的, 树$ T $如图 1所示, 此时$ \vert P\vert \geq 2l+1 $.

若$ s=1 $, 由上面的叙述可知: 当$ \vert S_1\vert = \vert S_2\vert= \cdots= \vert S_{k-2}\vert=l $时, $ P $是这类树$ T $的最长路中最短的, 树$ T $如图 2所示, 此时$ \vert P\vert \geq 2l+2 $.

若$ s\geq 2 $, 由上面的叙述可知: 当$ \vert S_1\vert = \vert S_2\vert= \cdots= \vert S_{i}\vert=l $, $ \vert S_{i+1}\vert = \cdots =\vert S_{k-2}\vert=l+1 $时, $ P $是这类树$ T $的最长路中最短的, 树$ T $如图 3所示, 此时$ \vert P\vert \geq 2l+3 $.

即

$ \vert P \vert \geq\left\{ \begin{array}{rcl} 2l+1 & & {s=0}\\ 2l+2 & & {s=1}\\ 2l+3 & & {s\geq 2} \end{array} \right.. $

由引理4可知，$ vcfc(T)\geq vcfc(P) $，那么

$ vcfc(T)\geq vcfc(P)\geq \left\{ \begin{array}{rcl} \lceil log_2(2l+2)\rceil & &{s=0}\\ \lceil log_2(2l+3)\rceil & &{s=1}\\ \lceil log_2(2l+4)\rceil & &{s\geq 2} \end{array} \right.. $

定理2  设$ T \in \mathcal{T}_{n, k} $, $ vcfc_{{\rm{max}}}(T)={\rm{max}}\{vcfc(T):T\in \mathcal{T}_{n, k}\} $, 那么$ \lceil {\rm{log}}_2(n-k+3) \rceil \le vcfc_{{\rm{max}}}(T) \le \lceil {\rm{log}}_2(n-k+1)\rceil+1 $.

证 先证$ vcfc_{{\rm{max}}}(T)\geq \lceil {\rm{log}}_2(n-k+3)\rceil $. 由引理4可知, $ vcfc_{{\rm{max}}}(T)\geq vcfc(P) $, 其中$ P $是$ T $中的最长路. 因为$ T \in \mathcal{T}_{n, k} $, 显然$ T $的最长路为$ P_{n-k+2} $, 则$ vcfc_{{\rm{max}}}({T})\geq vcfc(P_{n-k+2}) $ $ =\lceil {\rm{log}}_2(n-k+3)\rceil $.

下证$ vcfc_{{\rm{max}}}(T)\le \lceil {\rm{log}}_2(n-k+1)\rceil+1 $. 令$ T'=T-\{v_1, v_2, \cdots, v_{k} $$ |v_i $是$ T $的叶子$ \}$, 显然$ T' $是阶为$ n-k $的树. 我们对$ T $定义一种着色: $ T $中与$ T' $相同的点着色与$ T' $相同, 其它点着颜色$ vcfc(T')+1 $. 显然, 树$ T $中的任意两点间都有一条无矛盾点连通路, 从而$ vcfc_{{\rm{max}}}(T)\le vcfc(T')+1 $. 由引理3可知, $ vcfc(T')\le vcfc(P_{n-k}) $, 因此$ vcfc_{{\rm{max}}}(T)\le vcfc(T')+1\le vcfc(P_{n-k})+1= \lceil {\rm{log}}_2(n-k+1)\rceil+1 $, 证毕.

注1  在定理2中，设$ n=8 $, $ k=3 $, 如图 4所示, 此时$ vcfc(T)=4= \lceil {\rm{log}}_2(n-k+1)\rceil+1 $. 设$ n=7 $, $ k=3 $, 如图 5所示, 此时$ vcfc(T)=3= \lceil {\rm{log}}_2(n-k+3) \rceil $, 即定理2中的上界和下界是可以取到的.

注2  在定理2中, 设$ n-k=2^l-s(s=1 $或$ s=2) $, 则$ n-k+2=2^l $或$ 2^l+1 $. 如图 6所示, 令$ P_{n-k}=v_{k+1}\cdots v_{n} $, 则$ vcfc(P_{n-k})=\lceil {\rm{log}}_2(n-k+1)\rceil=l $. 令$ P=v_1v_{k+1}\cdots v_2 $, 那么$ vcfc(P)=\lceil {\rm{log}}_2(n-k+3)\rceil=l+1=\lceil {\rm{log}}_2(n-k+1)\rceil+1 $. 由引理4可知, $ vcfc(T)\geq vcfc(P) $, 其中$ P $是$ T $最长路, 因此$ vcfc(T)\geq\lceil {\rm{log}}_2(n-k+3)\rceil $. 对树$ T $定义一种着色: 用中心点着色法对$ P_{n-k} $进行着色, 其它点着颜色$ vcfc(P_{n-k})+1 $. 显然, 树$ T $任意两点间都有一条无矛盾点连通路, 那么$ vcfc(T)\le vcfc(P_{n-k})+1=\lceil {\rm{log}}_2(n-k+1)\rceil+1 $. 在此种情况下的树$ T $有$ vcfc(T)=\lceil {\rm{log}}_2(n-k+3)\rceil=\lceil {\rm{log}}_2(n-k+1)\rceil+1 $, 即定理2中的上界和下界是可以同时取到的.

在上述定理中, 我们对$ \mathcal{T}_{n.k} $关于无矛盾点连通数的上界和下界进行了讨论. 下面将对$ \mathcal{T}_{n}^{\Lambda} $关于无矛盾点连通数的上界进行了讨论, 得到如下结论:

定理3  设$ T\in \mathcal{T}_{n}^{\Lambda} $, 那么$ vcfc(T)\le \lceil {\rm{log}}_2(n-\Lambda +1)\rceil +1 $.

证 因为$ T\in \mathcal{T}_{n}^{\Lambda} $, 那么$ T $一定存在点$ v $满足$ d_T(v)=\Lambda $. 在$ T $中删除点$ v $, 将有$ \Lambda $个连通分支, 记为$ D_1 $, $ D_2 $, $ \cdots $, $ D_{\Lambda} $. 令$ v_i\in leaf(T)\cap V(D_i) $, $ T'=T-\{v_1, v_2, \cdots, v_{\Lambda}\} $, 显然$ T' $是阶为$ n-\Lambda $的树. 我们对$ T $定义一种着色: $ T $中与$ T' $中相同的点着色与$ T' $相同, 其它点着颜色$ vcfc(T')+1 $. 显然, 树$ T $中的任意两点间都有一条无矛盾点连通路, 从而$ vcfc(T)\le vcfc(T')+1 $. 由引理3可知, $ vcfc(T')\le vcfc(P_{n-\Lambda}) $, 因此$ vcfc(T)\le vcfc(T')+1\le vcfc(P_{n-\Lambda})+1=\lceil {\rm{log}}_2(n-\Lambda +1)\rceil +1 $, 证毕.

注3  如图 7所示, 设$ n-\Lambda=2^l-s(s=1 $或$ s=2) $, 则$ n-\Lambda+2=2^l $或$ 2^l+1 $. 令$ P_{n-\Lambda}=v_{\Lambda+1}\cdots v_{n} $, 则$ vcfc(P_{n-\Lambda})=\lceil {\rm{log}}_2(n-\Lambda+1)\rceil=l $. 令$ P=v_1v_{\Lambda+1}\cdots v_2 $, 那么$ vcfc(P)=\lceil {\rm{log}}_2(n-\Lambda+3)\rceil=l+1=\lceil {\rm{log}}_2(n-\Lambda+1)\rceil+1 $. 由引理4可知, $ vcfc(T)\geq vcfc(P) $, 其中$ P $是$ T $最长路, 从而$ vcfc(T)\geq\lceil {\rm{log}}_2(n-\Lambda+3)\rceil=\lceil {\rm{log}}_2(n-\Lambda+1)\rceil+1 $. 对树$ T $定义一种着色: 用中心点着色法对$ P_{n-\Lambda} $进行着色, 其它点着颜色$ vcfc(P_{n-\Lambda})+1 $. 显然, 树$ T $任意两点间都有一条无矛盾点连通路, 从而$ vcfc(T)\le vcfc(P_{n-\Lambda})+1=\lceil {\rm{log}}_2(n-\Lambda+1)\rceil+1 $. 因此在此种情况下的树$ T $有$ vcfc(T)=\lceil {\rm{log}}_2(n-\Lambda+1)\rceil+1 $, 即定理3中的上界是可以取到的.

在[8, 10]中, 作者对高度为$ d $且阶为$ 2^d-1 $的完全二叉树$ B_d $以及二叉树关于无矛盾点连通数的上界进行了讨论, 在此将其推广到$ \mathcal{T}_{\Lambda} $和$ \Lambda_d $中, 得到以下结论:

定理4  设$ T\in \mathcal{T}_{\Lambda} $, 当$ \Lambda=3 $且$ d=9 $时, 那么$ vcfc(T)\le8 $.

证 对树$ T $定义一种着色: 第一层着颜色$ 1 $且第二层着颜色$ 2 $. 将已经着过颜色的点删掉, 将会得到$ 6 $个$ B_7 $的子树. 在每一个子树中, 每一层的着色是一样的. 从上至下, 第$ 1 $个$ B_7 $用颜色$ 3, 4, 5, 6, 7, 1, 2 $, 如图 8所示, 其它5个$ B_7 $着色方式与第1个类似. 第2个$ B_7 $用颜色$ 4, 5, 6, 7, 8, 1, $ $ 2 $, 第3个$ B_7 $用颜色$ 5, 6, 7, 8, 3, 1, 2 $, 第4个$ B_7 $用颜色$ 6, 7, 8, 3, 4, 1, 2 $, 第5个$ B_7 $用颜色$ 7, 8, 3, 4, 5, 1, $ $ 2 $, 第6个$ B_7 $用颜色$ 8, 3, 4, 5, 6, 1, 2 $. 显然, 树$ T $的任意两点间都存在一条无矛盾的点连通路, 从而$ vcfc(T)\le 8 $, 证毕.

定理5  设$ T\in \mathcal{T}_{\Lambda} $, 当$ \Lambda=3 $且$ d=2(r+1)+5r $时, 那么$ vcfc(T)\le 6r+2 $.

证 当$ d=16 $时, 即在定理4的结构中加7层, 而此时后7层的结构为192组与定理4中相同的6个$ B_7 $子树, 我们将对其进行着色. 对其中1组进行着色, 其它191组与之相同. 在每一个子树中, 每一层的着色是一样的. 从上至下, 第1个$ B_7 $用颜色$ 9, 10, 11, 12, 13, 1, 2 $, 第2个$ B_7 $用颜色$ 10, 11, 12, 13, 14, 1, 2 $, 第3个$ B_7 $用颜色$ 11, 12, 13, 14, 9, 1, 2 $, 第4个$ B_7 $用颜色$ 12, 13, 14, 9, 10, 1, $ $ 2 $, 第5个$ B_7 $用颜色$ 13, 14, 9, 10, 11, 1, 2 $, 第6个$ B_7 $用颜色$ 14, 9, 10, 11, 12, 1, 2 $, 那么此类树有$ 16 $层和$ 14 $种颜色. 重复运用前面的过程, 颜色$ 1, 2 $着色$ 2(r+1) $层且$ r $组不相交的$ 6 $种颜色着色$ 5r $层, 因此此类树$ T $有$ 2(r+1)+5r $层和$ 6r+2 $种颜色. 容易验证树$ T $中任意两点间都有一条无矛盾的点连通路, 从而$ vcfc(T)\le 6r+2 $, 证毕.

定理6  设$ T\in \mathcal{T}_{\Lambda} $, 当$ d=2(r+1)+[\Lambda(\Lambda-1)-1]r $时, 那么$ vcfc(T)\le \Lambda(\Lambda-1)r+2 $.

证 对树$ T $定义一种着色: 先考虑前$ \Lambda(\Lambda-1)+3 $层, 第一层着颜色$ 1 $和第二层着颜色$ 2 $. 删除已经着色的点将会剩下$ \Lambda(\Lambda-1) $个$ (\Lambda-1)_{\Lambda(v-1)-1} $子树. 对这$ \Lambda(\Lambda-1) $个子树进行着色, 在每一个子树中, 每一层的着色是一样的. 从上至下, 第1个子树用颜色$ 3, 4, \cdots, \Lambda(\Lambda-1)+1, 1, 2 $, 第2个子树用颜色$ 4, 5, \cdots, \Lambda(\Lambda-1)+2, 1, 2 $, $ \cdots $, 第$ \Lambda(\Lambda-1) $个子树用颜色$ \Lambda(\Lambda-1)+2, 3, 4, \cdots, \Lambda(\Lambda-1), 1, 2 $. 重复前面过程, 颜色1, 2着色$ 2(r + 1) $层且$ r $组不相交的$ \Lambda(\Lambda-1) $种颜色着色$ [\Lambda(\Lambda-1)-1]r $层, 因此此类树$ T $有$ 2(r+1)+[\Lambda(\Lambda-1)-1]r $层和$ \Lambda(\Lambda-1)r+2 $种颜色. 容易验证树$ T $中任意两点间都有一条无矛盾的点连通路, 从而$ vcfc(T)\le 6r+2 $, 证毕.

$ \Lambda_d $与$ \mathcal{T}_{\Lambda} $的结构类似但不完全相同, 区别在于$ \Lambda_d $中第$ 2\sim d-1 $层的点的度为$ \Lambda+1 $而$ \mathcal{T}_{\Lambda} $的点的度为$ \Lambda $, 类似于$ \mathcal{T}_{\Lambda} $, 对于$ \Lambda_d $可以得到下面结论:

定理7  设$ T\in \Lambda_d $, 当$ d=2(r+1)+(\Lambda^2-1)r $时, 那么$ vcfc(T)\le \Lambda^2r+2 $.

定理8  设$ T $是阶为$ n(n\geq 2) $的树, 那么$ vcfc(T)\le d_V(T) $.

证 只需证明在算法1的着色条件下, 对于树中的每一对不同的顶点$ u $, $ v $都存在一条无矛盾连通路. 由于由两个相邻顶点组成的路总是无矛盾的, 我们可以假设$ u $和$ v $是不相邻的. 设$ v_0 $是首先将$ u $和$ v $分开的平衡点, 因为在$ u $和$ v $之间的路上$ v_0 $的颜色是最小的也是唯一的, 所以$ u $和$ v $之间的路是无矛盾的. 因此, 这是$ T $的一个无矛盾点连通, 即$ vcfc(T)\le d_V(T) $.

由定理6、7、8可知, $ \mathcal{T}_{\Lambda} $和$ \Lambda_d $关于无矛盾点连通数的上界与高度有关, 于是得到以下定理:

定理9  设$ T\in \mathcal{T}_{\Lambda} $, 那么

$ vcfc(T)\le\left\{ \begin{array}{ll} \Lambda(\Lambda-1)r+2 & d=2(r+1)+[\Lambda(\Lambda-1)-1]r\\ d & d\neq2(r+1)+[\Lambda(\Lambda-1)-1]r \end{array} \right.. $

定理10  设$ T\in \Lambda_{d} $, 那么

$ vcfc(T)\le\left\{ \begin{array}{ll} \Lambda^2r+2 & d=2(r+1)+(\Lambda^2-1)r\\ d & d\neq 2(r+1)+(\Lambda^2-1)r \end{array} \right.. $