在图$G=(V(G), E(G))$中, $V(G)$, $E(G)$分别表示图$G$的顶点集合, 边集合.图$G$的一个$k$ -边正常染色是指一个映射$f:E(G)\rightarrow\{1, 2, \cdots, k\}$, 使得对于任何两个相邻的边$e_{1}$, $e_{2}$, 均有$f(e_{1})\not=f(e_{2})$, 图$G$的$k$ -边正常染色又简称为$k$ -边染色.设$G$是一个图, $e_{1}=u_{1}v_{1}$, $e_{2}=u_{2}v_{2}$是图$G$中的两条边.若$e_{1}$与$e_{2}$相邻, 则称$e_{1}$与$e_{2}$的距离为0, 若$e_{1}$与$e_{2}$不相邻, 从$e_{1}$的一个端点到$e_{2}$的一个端点的路称为$e_{1}$到$e_{2}$的一条路. $e_{1}$与$e_{2}$的距离是指在$e_{1}$到$e_{2}$的所有路中一条最短路所含的边数.图$G$的$k$ -强边染色是一种$k$ -正常染色, 使得任意相邻于同一条边的两条边不得染相同的颜色.换句话说, 图$G$的强边染色是一种边染色, 使得任意两条距离不大于1的边被染不同颜色.图$G$的强边色数$\chi_{s}^{'}(G)$是最小的$k$, 使得$G$有一个$k$ -强边染色.
1985年, Erdös和Nešetǐil[1]给出了关于强边染色的概念, 并提出了如下猜想:对于最大度为$\Delta_{G}$的图$G$, $\chi_{s}^{'}(G)\leqslant\frac{5}{4} \Delta_{G}^{2}$. Molloy和Reed[2]证明了当$\Delta_{G}$足够大时, $\chi_{s}^{'}(G)\leqslant(2-\epsilon)\Delta_{G}^{2}$, 这里$\epsilon$约为$\frac{1}{50}$.而Bruhn和Joos[3]进一步证明了$\chi_{s}^{'}(G)\leqslant1.93\Delta_{G}^{2}$; Andersen[4]证明了一个$3$ -正则图$G$的强边色数$\chi_{s}^{'}(G)\leqslant10$.
麦比乌斯梯子$C(2n, n)$是这样一个图, 它的顶点集为$V=\{v_{i}\mid i=1, 2, \cdot\cdot\cdot, 2n\}$, 边集为$E=\{v_{i}v_{i+1}$, $v_{i}v_{i+n}\mid i=1, 2, \cdot\cdot\cdot 2n\}$, 这里的加法在取模$2n$的情况下进行.它是一个$3$ -正则图, 可以嵌入在射影平面上, 当$n=3$时, $C(2n, n)$就是$K_{3, 3}$.
本文研究了$C(2n, n)$的强边色数, 得到如下结果:当$n=3$时, $\chi_{s}^{'}(C(2n, n))=9$; 当$n=4$时, $\chi_{s}^{'}(C(2n, n))=10$; 当$n=5, 8$时, $\chi_{s}^{'}(C(2n, n))=8$; 当$n\geqslant3$且$n\equiv2~($mod$~4)$时, $\chi_{s}^{'}(C(2n, n))=6$; 当$n\geqslant7$且$n\equiv0, 1$或$3~($mod$~4)$时, $\chi_{s}^{'}(C(2n, n))=7$.
在本节的开始, 先给出$C(2n, n)$的强边色数的一个下界.
当$n=2$时, $C(2n, n)$即为$K_{4}$, 因为$K_{4}$中任意两条边之间的距离都小于$2$, 且$K_{4}$含有$6$条边, 所以$\chi_{s}^{'}(C(4, 2))=6$.接下来, 考虑$n\geqslant3$的情形.
引理2.1 当$n\geqslant3$时, $\chi_{s}^{'}(C(2n, n))\geqslant6$.
证 当$n\geqslant3$时, $C(2n, n)$有一个导出子图同构于如图 1所示的图$H$.不难发现图$H$中任何两条边之间的距离都不大于$1$.因图$H$含有$6$条边, 故$\chi_{s}^{'}(H)\geqslant6$, 从而$\chi_{s}^{'}(C(2n, n))\geqslant6$.
引理2.2 当$n\geqslant3$时, $\chi_{s}^{'}(C(2n, n))=6$当且仅当$n\equiv2~($mod$~4)$.
证 充分性 设$n\equiv2~($mod$~4)$, 欲证$\chi_{s}^{'}(C(2n, n))=6$.
由引理$2.1$知$\chi_{s}^{'}(C(2n, n))\geqslant6$, 故只需证$\chi_{s}^{'}(C(2n, n))\leqslant6$.此时, 只需给出$C(2n, n)$的一种只含有6种颜色的强边染色.现定义$C(2n, n)$的一个边染色$f:E(C(2n, n))\rightarrow\{1, 2, 3, 4, 5, 6\}$, 如下: $f(v_{i}v_{n+i})=1~ (i=1, 3, 5\cdots, n-1);$ $f(v_{i}v_{i+1})=2~ (i=1, 5, 9, \cdots, 2n-3);$ $f(v_{1}v_{2n})=f(v_{i}v_{i+1})=3~(i=4, 8, 12, \cdots, 2n-4);$ $f(v_{i}v_{i+1})=4~(i=3, 7, 11, \cdots, 2n-1);$ $f(v_{i}v_{i+1})=5~(i=2, 6, 10, \cdots, 2n-2);$ $f(v_{i}v_{n+i})=6~(i=2, 4, 8, \cdots, n).$不难验证$f$符合强边染色的定义, 所以当$n\equiv2~($mod$~4)$时, $\chi_{s}^{'}(C(2n, n))\leqslant6$.
必要性 设$\chi_{s}^{'}(C(2n, n))=6$, 欲证$n\equiv2~($mod$~4)$.
只需证明当$n\not\equiv2~($mod$~4)$时, $\chi_{s}^{'}(C(2n, n))\not=6$.
当$n\equiv0~($mod$~4)$时, 假设$\chi_{s}^{'}(C(2n, n))=6$.此时, 存在$C(2n, n)$的一个强边染色$f:E(G)\rightarrow\{1, 2, 3, 4, 5, 6\}$.首先边$v_{1}v_{2}$, $v_{1}v_{n+1}$, $v_{1}v_{2n}$, $v_{2}v_{2+n}$, $v_{n+1}v_{n+2}$, $v_{n}v_{n+1}$中的任一条边都需要染不同的颜色, 因为在这些边中任意两条边之间的距离都小于2.不妨设$f(v_{1}v_{n+1})=1, f(v_{1}v_{2})=2, f(v_{1}v_{2n})=3, f(v_{n+1}v_{n+2})=4, f(v_{n}v_{n+1})=5, f(v_{2}v_{n+2})=6.$因为$v_{2}v_{3}$与边$v_{1}v_{2}$, $v_{1}v_{n+1}$, $v_{1}v_{2n}$, $v_{2}v_{2+n}$, $v_{n+1}v_{n+2}$之间的距离都小于2, 而与$v_{n}v_{n+1}$的距离等于2, 所以$f(v_{2}v_{3})=5$.同样的, $f(v_{1}v_{2n})=f(v_{n+2}v_{n+3})=3, $ $f(v_{1}v_{n+1})=f(v_{3}v_{n+3})=1, $ $f(v_{n+1}v_{n+2})=f(v_{3}v_{4})=4, $ $f(v_{n+3}v_{n+4})=f(v_{1}v_{2})=2, $ $f(v_{4}v_{n+4})=f(v_{2}v_{n+2})=6.$对剩下的边染色, 每一条边只有一种颜色可染.染色规律如下
此时会发现, 因为$n\equiv0~($mod$~4)$, 所以$f(v_{n-1}v_{n})=4$, 而$f(v_{n+1}v_{n+2})=4$, 但两边之间的距离为1, 这与强边染色的定义相矛盾, 故当$n\equiv0~($mod$~4)$时, $\chi_{s}^{'}(C(2n, n))\not=6$.同理, 当$n\equiv1$或$3~($mod$~4)$时, $\chi_{s}^{'}(C(2n, n))\not=6$.
定理2.3 当$n\not\equiv2~($mod $4)$时,
证 当$n=3$时, 在$C(6, 3)$中, 任两条边之间距离都小于2.所以一种颜色只能染一条边, 又$C(6, 3)$有9条边, 所以$\chi_{s}^{'}(C(6, 3))=9$.
当$n=4$时, 在$C(8, 4)$中, 圈$D=v_{1}v_{2}v_{3}\cdots v_{8}v_{1}$中任何两条边的距离都小于2.因圈$D$有8条边, 故对圈$D$强边染色至少需要8种颜色.又因$D$中任何一边与$C(8, 4)$中除$D$以外的边的距离都小于2, 故染剩下的边所用的颜色和圈$D$所用的颜色不同.在剩下的4条边中, 存在两条边之间的距离小于等于1, 故剩下的4条边至少需要两种颜色.综上所述, $C(8, 4)$进行强边染色至少需要10种颜色, 即$\chi_{s}^{'}(C(8, 4))\geqslant10$.现定义$C(8, 4)$的一个边染色$f:E(C(8, 4))\rightarrow\{1, 2, \cdots, 10\}$, 如下: $f(v_{1}v_{2})=1, $ $f(v_{2}v_{3})=2, $ $f(v_{3}v_{4})=3, $ $f(v_{4}v_{5})=4, $ $f(v_{5}v_{6})=5, $ $f(v_{6}v_{7})=6, $ $f(v_{7}v_{8})=7, $ $f(v_{8}v_{1})=8, $ $f(v_{1}v_{5})=f(v_{3}v_{7})=9, $ $f(v_{2}v_{6})=f(v_{4}v_{8})=10.$不难验证$f$是一个强边染色, 即$\chi_{s}^{'}(C(8, 4))\leqslant10$, 所以$\chi_{s}^{'}(C(8, 4))=10$.
当$n=5$时, 由引理$2.1$与$2.2$知$\chi_{s}^{'}(C(10, 5))\geqslant7$.现假设$\chi_{s}^{'}(C(10, 5))=7$.则存在一个强边染色$f:E(C(10, 5))\rightarrow\{1, 2, 3, 4, 5, 6, 7\}$.为讨论方便, 称圈$A=v_{1}v_{2}v_{3}\cdots v_{10}v_{1}$上的边为第一类边, 其余的边为第二类边.因为圈$A$上任意三条边中, 存在两条边使得它们之间的距离小于等于1, 故当一种颜色所染的边都是第一类边时, 这种颜色至多染两条边.因为第二类边的任意三条边中, 存在两条边使得它们之间的距离小于等于1, 故当一种颜色所染的边都是第二类边时, 这种颜色至多染两条边.当一种颜色所染的边既有第一类边又有第二类边时, 不妨设所用的颜色为1, 且$v_{1}v_{2}$被颜色1所染, 即$f(v_{1}v_{2})=1$, 此时第二类边中, 只有$v_{4}v_{9}$可染与$v_{1}v_{2}$相同的颜色, 那么颜色1至多可染两条边.
综上所述, 任一种颜色在$C(10, 5)$中所染的边数不能大于等于3.因为$C(10, 5)$共有15条边, 且$\chi_{s}^{'}(C(10, 5))=7$, 所以至少存在一种颜色所染的边数要大于等于$3$.故产生矛盾.故$\chi_{s}^{'}(C(10, 5))\geqslant8$, 现定义$C(10, 5)$的一个边染色$g:E(C(10, 5))\rightarrow\{1, 2, 3, 4, 5, 6, 7, 8\}$, 如下$g(v_{1}v_{6})=g(v_{4}v_{9})=1, $ $g(v_{1}v_{2})=g(v_{8}v_{9})=2, $ $g(v_{1}v_{10})=g(v_{7}v_{8})=3, g(v_{6}v_{7})=g(v_{3}v_{4})=4, $ $g(v_{5}v_{6})=g(v_{3}v_{8})=5, $ $g(v_{2}v_{7})=g(v_{5}v_{10})=6, $ $g(v_{4}v_{5})=7, $ $g(v_{2}v_{3})=g(v_{9}v_{10})=8.$不难验证边染色$g$是一个强边染色, 即$\chi_{s}^{'}(C(10, 5))\leqslant8$.故$\chi_{s}^{'}(C(10, 5))=8$.
当$n=8$时, 由引理$2.1$与$2.2$知$\chi_{s}^{'}(C(16, 8))\geqslant7$.现假设$\chi_{s}^{'}(C(16, 8))=7$.则存在一个强边染色$f:E(C(16, 8))\rightarrow\{1, 2, 3, 4, 5, 6, 7\}$.为讨论方便, 称圈$C=v_{1}v_{2}v_{3}\cdots v_{16}v_{1}$上的边为第一类边, 其余的边为第二类边.因为圈$C$上任意四条边中, 存在两条边使得它们之间的距离小于等于1, 故当一种颜色所染的边都是第一类边时, 这种颜色至多染三条边.因为第二类边的任意五条边中, 存在两条边使得它们之间的距离小于等于1, 故当一种颜色所染的边都是第二类边时, 这种颜色至多染四条边.当一种颜色所染的边既有第一类边又有第二类边时.不妨设所用的颜色为1, 且$v_{1}v_{2}$被颜色1所染.即$f(v_{1}v_{2})=1$.此时第二类边中, $f(v_{4}v_{12})$, $f(v_{5}v_{13})$, $f(v_{6}v_{14})$, $f(v_{7}v_{15})$可以等于1, 当$f(v_{4}v_{12})=1$时, 剩下边$f(v_{6}v_{7})$, $f(v_{7}v_{8})$, $f(v_{6}v_{14})$, $f(v_{7}v_{15})$, $f(v_{14}v_{15})$可以等于1, 但这五条边中, 任意两边之间的距离都小于2, 故只有一条边可染与$v_{1}v_{2}$相同的颜色, 故颜色1至多染三条边.故任一种颜色所染的边既有第一类边又有第二类边时, 这种颜色至多能染三条边.
综上所述, 任一颜色在$C(16, 8)$中至多染四条边.此时, 设$x$为只染第二类边的颜色数目.当$x=0$时, 因为$\chi_{s}^{'}(C(16, 8))=7$, 所以7种颜色至多染$7\times3=21$条边.当$x=1$时, 至多染$1\times4+(7-1)\times3=22$条边.当$x=2$时, 至多染$2\times4+(7-2)\times3=23$条边.当$x\geqslant3$时, 因为只有八条第二类边, 至多染$8+(7-x)\times3\leqslant20$条边.而$C(16, 8)$有24条边, 所以与假设矛盾.故$\chi_{s}^{'}(C(16, 8))\geqslant8$, 现定义$C(16, 8)$的一个边染色$h:E(C(16, 8))\rightarrow\{1, 2, \cdots, 8\}$, 如下: $h(v_{1}v_{9})=h(v_{3}v_{11})=h(v_{5}v_{13})=h(v_{7}v_{15})=1, $ $h(v_{1}v_{2})=h(v_{11}v_{12})=h(v_{6}v_{7})=2, $ $h(v_{1}v_{16})=h(v_{10}v_{11})=h(v_{4}v_{5})=3, $ $h(v_{3}v_{4})=h(v_{9}v_{10})=h(v_{14}v_{15})=4, $ $h(v_{2}v_{3})=h(v_{8}v_{9})=h(v_{12}v_{13})=5, $ $h(v_{2}v_{10})=h(v_{4}v_{12})=h(v_{6}v_{14})=h(v_{8}v_{16})=6, $ $h(v_{5}v_{6})=h(v_{15}v_{16})=7, h(v_{7}v_{8})=h(v_{13}v_{14})=8.$不难验证$h$是一个强边染色, 即$\chi_{s}^{'}(C(16, 8))\leqslant8$.故$\chi_{s}^{'}(C(16, 8))=8$.
当$n\equiv0~($mod$~4)$时, 由引理$2.1$与$2.2$知$\chi_{s}^{'}(C(2n, n))\geqslant7$.下面证$\chi_{s}^{'}(C(2n, n))\leqslant7$.为此先给出$C(24, 12)$的一个有7种颜色的强边染色, 如图 2所示.而当$n>12$时, 只需将图$2$中的边$v_{6}v_{7}$与$v_{n+6}v_{n+7}~(n=4k, k\geqslant3)$删除, 并将点$v_{6}$, $v_{n+6}$, 分别与图 3中的点$a$, $b$粘合, 并分别将点$v_{7}$, $v_{n+7}$与$c$, $d$之间连一条边, 然后令$f(c~v_{7})=2$, $f(d~v_{n+7})=4$, 即可得到$C(2n, n)~(n=4k, k>3)$的强边色数.
当$n\equiv1~($mod$~4)$时, 由引理$2.1$与$2.2$知$\chi_{s}^{'}(C(2n, n))\geqslant7$.下面证明$\chi_{s}^{'}(C(2n, n))\leqslant7$, 为此先给出$C(18, 9)$的一个有7种颜色的强边染色.如图 4所示.而当$n>9$时, 只需将图$4$中的边$v_{7}v_{8}$与$v_{n+7}v_{n+8}~(n=4k+1, k\geqslant2)$删除, 并将点$v_{7}$, $v_{n+7}$分别与图 5中的点$a$, $b$粘合, 并分别将点$v_{8}$, $v_{n+8}$与$c$, $d$之间连一条边, 然后令$f(c~v_{8})=3$, $f(d~v_{n+8})=5$, 即可得到$C(2n, n)~(n=4k+1, k>2)$的强边色数.
当$n\equiv3~($mod $4)$时, 由引理$2.1$与$2.2$知$\chi_{s}^{'}(C(2n, n))\geqslant7$.下面证明$\chi_{s}^{'}(C(2n, n))\leqslant7$, 为此先给出$C(14, 7)$的一个有7种颜色的强边染色.如图 6所示.而当$n>7$时, 只需将图$6$中的边$v_{6}v_{7}$与$v_{n+6}v_{n+7}~(n=4k+3, k\geqslant1)$删除, 并将点$v_{6}$, $v_{n+6}$分别与图 7中的点$a$, $b$粘合, 并分别将点$v_{7}$, $v_{n+7}$与$c$, $d$之间连一条边, 然后令$f(c~v_{7})=2$, $f(d~v_{n+7})=4$, 即可得到$C(2n, n)~(n=4k+3, k>1)$的强边色数.
2018, Vol. 38 Issue (3): 497-501
PDF
2018, Vol. 38 Issue (3): 497-501 PDF