强边着色猜想问题的最优图.PDFVIP

第３４卷第３期 重庆工商大学学报（自然科学版） ２０１７年６月 Ｖｏｌ．３４　ＮＯ．３　　　　　　　　ＪＣｈｏｎｇｑｉｎｇＴｅｃｈｎｏｌＢｕｓｉｎｅｓｓＵｎｉｖ（ＮａｔＳｃｉＥｄ）　 　　　　　　　 Ｊｕｎ．２０１７ － ｄｏｉ：１０．１６０５５／ｊ．ｉｓｓｎ．１６７２０５８Ｘ．２０１７．０００３．００５ 强边着色猜想问题的最优图 张卫 标 （商丘学院计算机工程学院，河南 商丘４７６０００） 　　摘　要：著名图论专家Ｅｒｄｓ和Ｎｅｅｔǐｉｌ对图的强边色数上界提出了一个猜想：当最大度 为偶数时， Δ ５ １ ２ ２ χ χ － ＋ ＝ ′（Ｇ） ；当最大度 为奇数时，′（Ｇ） （５ ２ １）；并且给出了当 ４时的最优图．此处构造了 ≤ Δ Δ ≤ Δ Δ Δ ｓ ４ ｓ ４ 一族图，并证明了当最大度为奇数时，如果Ｅｒｄｓ和Ｎｅｅｔǐｉｌ提出的强边着色猜想成立，则猜想中的上界是最 优的． 关键词：边着色；强边着色；最优图 中图分类号：Ｏ１５７．５　　　文献标志码：Ａ　　　文章编号：１６７２０５８Ｘ（２０１７）０３００２１０３ 　　所涉及的图均为无向有限图，未介绍的术语和 记号请参见文献［１２］．图Ｇ的边着色是指在图Ｇ中 任意两条相邻的边均不着相同的颜色．强边着色是 指图Ｇ的边着色，并且要求任意长为３的路上的边 不能着一样的颜色．一个图Ｇ的强边色数是指 Ｇ中 χ 所有强边着色中所用色数的最小者，记为 ′（Ｇ）．关 ｓ 于强边着色问题，很多国内外学者已取得了很多好 ［３７］ 的结果 ． 强边着色猜想中使得等式成立的图叫做最 优图． 图１　最大度为４的最优图 ＝ Ｆｉｇ．１　Ｏｐｔｉｍａｌｇｒａｐｈｗｉｔｈｍａｘｉｍｕｍｄｅｇｒｅｅｏｆ４ Ｅｒｄｓ和Ｎｅｅｔǐｉｌ给出了当 ４时的最优图，如 Δ 图（１）所示，记为Ｇ．从图１中可以看出，图Ｇ 的边 １ １ 色数等于强着色猜想的上界，即为最优图． ＝ 数Ｅ（Ｇ） ２０，且 Ｇ 中任意两边都在长为３的路 １ １ 证明　构造了一个这样的图，记为 Ｇ，如图２ ２ ５ ２ χ ＝ ＝ ＝ 所示，可以看出图２中任意两边都在长为３的路上， 上，所以 ′（Ｇ） ２０ ，Ｇ 即为 ４时的最 ｓ １ Δ １ Δ ４ １ ２