平面图的强边色数研究

摘要

图G的强边色数，记为x's(G)，是最小的正整数k,使得图G存在满足下述条件的k-边着色：每一种颜色的所在的边集（色类）构成该图的一个导出匹配.本论文仅考虑简单图.对一个图G,我们用Δ=Δ(G)表示图G的最大度.本硕士论文主要研究平面图的强边色数.我们的研究目标是要证明下述猜想：对任一平面图G,均有X's(G)≤Δ2.针对这一研究目标，我们利用反证法建立了极小反例的若干结构性质，并由此得到使得该猜想成立的若干图类.在结构分析过程中，我们采用的一个重要工具是相异代表系（SDR). 本文的研究内容分为两部分.第一部分主要讨论使得猜想不成立的极小反例平面图G的结构性质，其中的极小反例平面图G满足：X's(G)≤Δ2+1并且|V(G)|+|E(G)|尽可能小.第二部分主要研究平面二部图及最大度大于等于8的平面图的强边色数问题.本文的主要结果如下： (1)若图G是平面二部图，则它的强边色数X's(G)<Δ2,其中Δ>7. (2)若图G是最大度A>8的平面图，则它的强边色数X's(G)≤Δ2 (3)极小反例平面图G不存在1度顶点. (4)若图G为极小反例平面图，则对任意的边xyeE(G),均有d(x)+d(y)≥Δ+2. (5)极小反例平面图G不存在3-圈，使得3-圈中包含2-顶点，3-顶点和4-顶点. (6)极小反例平面图G不存在4-圈，使得4-圈中包含2-顶点. (7)极小反例平面图G是2-连通的.

目录

第一个书签之前