（应用数学专业论文）图的l（pq）标号问题研究.pdf

s t u d yo nt h ep r o b l e m0 fl ( p ，q ) l a b e l i n go fg r a p h s a b s t r c t t h el ( p ，q ) 一l a b e l i go fg r a p h 8 盯i 8 e sf r o mav 私i a t i o nf r e q u e n c ya 8 s i g n m e n t p r o b l e mb yh a l e g i v e na 窜a p hga n dt w op o s i t i v ei n t e g e r 8p q ，a nm l ( p ，g ) 一 l 山e l i n go fgi 8af u n c t i o n ，：y ( g ) 一 o ，1 ，2 ，m ) s u c ht h a t ，f o ra n yt w 0 v e r t i c e 8 。，掣y ( g ) ，i ，( 茹) 一，( 剪) l pi fd g ( 。，掣) = 1 ；a n di ，( 罩) 一，( 掣) l g i f 奶( z ，暑，) = 2 t h el 0 ，g ) 一n u n l b e ro fg ，d e n o t e db ya m ( g ) ，i st h e8 m a l k 8 t n u m b e rms u c ht h a tgh a sa nm l ( n g ) 一i a b e l i n g i nt 1 1 i st h e 8 i 8 ，w e 丑r s t l y8 u m m a r i z et h em a i nr e s u l t sa n de v o l u t i o no nt h e l ( p ，q ) - l a b e l i n gi nr e c e n t ”a r 8 ，t h e nw e 、】l r i l l i n v e 8 t i g a t et h el ( 1 ，1 ) 一1 a b e l i n ga n d t h el ( 2 ，1 ) 一1 a b e l i n go ft h el i i l eg r a p hl ( g ) o fa8 i m p l eg r a p hg 札hm a 妇m 啪 d e g r e e ( g ) 4 w eu 8 u a u yd e n o t e db y 强口( g ) t h el ( p ，q ) 一l a b e u n gn u h l b e ro f l ( g ) f i n a u y w ee x p l o r et h el ( p ，q ) 一1 8 b e l i n gp r o b l e mo f8 0 m ec l 明8 e 8o fg r a p h 8 t h el ( 1 ，1 ) 一l a b e u n go fl ( g ) i 8a a i o g o l 】8t ot h e 骶r o n g e d g ec o l o 血go fg r 印h g w bd e n o t e dt h e8 t r o n ge d g ec h r o m a t i ci n d e x ( t h el i 8 ts t r o n ge d g ec h r o m a t i c i n d e x ) o fgb y 嵌7 ( g ) ( s 磁( g ) ) ，t h e ns x ，( g ) = a i 1 ( g ) + 1 i n1 9 8 5 ，e r d 6 8a n d 甜e t f 钉c 0 j e 毗u r e dt h 砒f o r 舭l y8 i m p l eg r 8 p hg ，s x 7 ( g ) 5 2 ( g ) 4w h e ( g ) i 8e 嘲舡l ds x ，( g ) 5 2 ( g ) 4 一( g ) 2 + l 4w h e n ( g ) i so d d b d r ( g ) = 4 ，t h ec o n j e c t u r e db o u n di 82 0 ，p r e v i o u s l nh o r 毛kp r o v e ds 一( g ) 2 3 f 0 r ( g ) = 3 ，t h ec o n j e c t t l r e db o u n di s1 0 ，t l l i 8b o u n dh 8 sb e e np r o v e db ya n d e r s o n ，a r l di n d e p e n d e n t i y ，h o r 矗ke ta 1 i nt h j 8t h e s i s ，w es h o wt h 8 ts 弼( g ) 2 2w h e n ( g ) = 4 f u r t h e r m o r e ，i f t h eg i r t hg ( g ) 4 ，t h e ns x ( g ) 2 1 s i n c es x 7 ( g ) s x ：( g ) ，8 0 v ei m p r o 、r e d t h er e 8 u l to fh o r 酞a 1 8 0 ，w ep r a v e dt h a ti f ( g ) = 3 ，t h e ns x ：( g ) 1 1 f o rg r a p hgw i t h ( g ) 4 ，g e o r g e sa n dm a u r 0p r o v e d 心l ( g ) s2 ( ( g ) 一 1 ) ( ( g ) + 2 ) w ji m p r a v e dt h i sb o u n dt ot h a ta ；1 ( g ) 2 2 ( g ) 一2 f i n a l l y w e 唧1 0 r et h el ( p q ) 一i a b e l i n go fk - d e g e n e r a t e da n dm - m 曲出e d8 u m g 1 m + 岛o fg 1 锄dg 2 1 np a r t i e l l l a r ，w ep r e s 龇ct h ea t t 咖a b l el d w 聊a n dt h e u p p e rb o u n d 8f o rc a c t u 丑a n du n i c y d e k e y w o r j d s ：l ( p ，q ) 一l a b e l i n g ，e d g e _ l ( p ，q ) 一l a b e u n g ，e d g e l ( p ，q ) 一咖l b e r 8 t r o n ge d g 争l o r i n g ，8 t r o n ge d g e c h r o m a t i cm m l b e r ，l i 8 t - 8 t r o n ge d g e c o l o r i i l g 8 t r o n ge d g e - c h o i c e 矾m b e r 第一章绪论 图论是组合数学的一个分支，在现实世界中存在广泛的应用它的起源很 早，瑞士数学家欧拉( l e l l l e r ) 在1 7 3 6 年解决了当时颇为有名的一个数学难题， 即哥尼斯城堡七桥”问题，从而使欧拉成为图论和拓扑学的创始人欧拉将七 桥问题转化为一个数学模型，用四个顶点表示两岸和两个小岛，连接相应顶点的 线段表示桥此论文的发表标志着图论的诞生 早期图论与“数学游戏”密切联系直到1 8 4 7 年，基尔霍夫( k i r 世吐f f l 运 用图论解决了电路理论中求解联立方程问题，第一次将图论运用于工程技术领 域1 8 5 7 年，凯莱( c a y l e y ) 在有机化学领域，计算饱和氢化物g 玩。+ 2 的同分 异构体数目时，发现了一族重要的图，称为树从此图论脱离解决“数学游戏” 阶段，进入解决各种实际问题，开始向其它科学领域渗透 2 0 世纪后，图论应用渗透到诸多其它科学领域，如物理学、化学、信息学、 运筹学、博奕论、计算机网络、社会学、语言学等 2 0 世纪5 0 年代，由于计算 机的迅速发展，促使了组合学最优化算法研究，有力推动了图论的发展，使图论 成为数学领域中发展最快的分支之一 图的染色是图论中重要组成部分，它来源于著名的四色猜想，在其它科学领 域和现实生活中有广泛的应用图染色这一迷人的研究领域，与概率论、矩阵 论、群论等有着密切的联系，同时包含着许多有趣的问题，从而吸引丁众多学者 的极大兴趣本学位论文将介绍图论中新的研究课题图的标号理论，它来源于无 线电领域。是某些图染色问题的推广，有着十分广泛的应用和研究价值 ( 一) 、应用背景 在1 9 8 0 年，h a l e 1 】提出了频率分配的理论及其应用频率分配问题来源于 现实世界无线电领域对于一个无线电发射台集合，当给每个发射台分配频率 时，会发现被分配相同或相近频率的发射台，由于地理位置相近或自然现象等原 因可能会产生干扰因此分配频率时就要使得相互干扰的无线电发射台所分配 的频率在允许范围之内，研究内容在于确定一种分配使它满足各种限制，并使某 些值最小化 h a l e 将此实际问题转化为图论问题构造图g ；( v ，e ) ，用顶点集合v ( g ) 申 顶点表示发射台。两个顶点之间存在一条边当且仅当对应的发射台相互干扰给 定图g 和非负整数集合t ，图g 的b 染色就是映射f ：y ( g ) - o ，l ，2 ， ，使 得 若。f ( g ) ，贝0i ，( 。) 一，( ”) ig t ! 二21 匡旦笪量 为了选到资源优化配置，主要围绕以下参数进行研究：( 1 ) t _ 染色的色鼓 ，( g ) ，耵( g ) = ”n n ，0 ) i z y ( g ) ) l i ，为g 的t - 染色 ；( 2 ) t - 染色的s p n 母酚( g ) ，5 p t ( g ) = m n m d z l ，( 茹) 一，( 掣) 。，目v ( g ) ) ，为g 的t - 染色) ；( 3 ) t 一染色的e d g e8 p 粕e s 阳( g ) ，e 印r ( 回= m 2 n m ( 1 ，( z ) 一，( 可) 1j 。可e ( g ) ) i ， 为g 的t i 染色) 这一理论与图论中正常顶点染色有机联系在一起当t = ( o ，t - 染色就是 图论中图的正常顶点染色问题，另外图染色的许多算法可以得到应用频率分配 问题作为最优化问题引起了许多学者的研究必趣。在过去的+ 几年得到广泛地 加以研究【3 7 ，3 8 ，3 9 l r d b e n 8 2 ( 和g r i g 窜的个人交流) 提出了另外一种相似的有效的频率分配办 洼，他提出在几个不圊地点的无线电发射台有效地分配无线电频率，频率用菲负 整数表示使得相近的发射台分配不同的频率，极相近的发射台分配频率至少相 差2 ，从而使得这些发射台不会干扰研究内容在于确定无线电现实网络需要最 少频率，就能使较近的无线电发射台不发生干扰g r i 鹳8 和m 【2 将这个问题 归结为圈的距离( 2 ，1 ) 标号闻题用图的顶点表示无线电发射台，如果图的两 个顶点相邻，表示两个无线电发射台非常相近如果图的两个顶点的距离为 2 ，表示两个无线电发射台相近更加准确给出以下定义； 定义1 1 1 令g 为图g 的一个l ( 2 ，1 ) 一标号是映射，：y ( g ) 0 。l ，2 ，) ， 使得对任意。，口ey ( g ) ，若如( z ，) = 1 则i ，( z ) 一，( 目) j 2 ；若d o ( z ，) = 2 则 i ，( z ) 一“笋) i 1 g 的一个m l ( 2 ，1 ) 一标号是标号，：v ( g ) 一 o ，l ，2 ，) ，使得 对任意y ( g ) ，有，( m ) m 并称沁。l ( a ) = m i n 刊存在g 的一个m l ( 2 ，1 ) 一标号 为图g 的l ( 2 ，1 ) - 数 推广图的l ( 2 ，1 ) 一标号的定义，图的慨q ) 一标号能够类似给出定义 2 ，3 定义l 1 2令g 为囤，a 口为两个正整数，芦q g 的一个l ( n 鼋) 一 标号是映射，：v ( g ) 一 o ，l ，2 ， ，使得对任意z ，口y ( g ) ，若d g ( 。，口) = l 则 1 ，( ) 一，( g ) i 蟊若d o ( ? ，笋) = 2 则i ，( z ) 一，( ”) j 兰口g 的一个m l ，g ) 一 标号是标号，：v ( 回 o ，1 ，2 ，) ，使得对任意o y g ) ，有，( 。) sm 并称 m ( g ) = n l i n m i 存在g 的一个m l 0 ，g ) 一标号 为图g 的厶( p ，g ) - 数 由于缺少无线电频率资源及光谱前使用密集化，因此优化频率资源配置及极 小化或消除频率的内在干扰，t - 染色及l ( p ，q ) 一标号闷题就显得十分有研究价 值许多学者致力于该钡域。得到许多有价值的结果，然而它的研究十分的困 难，因此存在大量问题尚未解决 ( 二) 、研究现状 ( 二) 、研究现状 3 本节总结近年来，关于标号理论的主要结果及进展首先介绍标号问题的复 杂性，其次介绍l ( p ，q ) 一标号数上界和下界 l ( 1 ，1 ) - 标号文献 4 ，5 】证明图的l ( 1 ，1 ) 一标号问题是n p 一完全问题同样， 在文献 6 给出对于平面图的l ( 1 ，1 ) 一标号问题是n p 一完全的对于图的l ( 1 ，1 ) 一 标号问题，寻找好的算法方面1 5 】给出一个近似比为o ( 、l y ( g ) i ) 的贪婪算法 另外一个具有近似比为0 ( ( g ) ) 的算法是给在文献 7 ，其中是 ( g ) 图的厚度 l ( 2 ，1 ) - 标号在文献【2 】证明图的l ( 2 ，1 ) 一标号问舾是n p 一完全问题并 且。作者猜想对于固定常数4 ，给出一个图g ，决定是否a ( g ) 七是n p 完 全的这个猜想在【8 】得以证明 l ( p ，q ) - 标号在文献【8 ) 作者猜测对于每个p q 1 ，存在一个k ( 依赖于p 和q ) 使得决定是否。( g ) 七是n p 完全的在这个猜想的支持下。作者证明 对于固定p g 1 ，决定是否a m ( g ) sp + q 腭1 是n p - 完全的对于任意固定 ：和p 2 q ，决定是否a 附( g ) p + 蛔是n p 一完全的对于任意固定p 2 9 和七 1 9 棚+ 2 p + 口，决定是否，q ( g ) 是n p 一完全的对于任意p 2 ，若 南p + 5 ，则l ( p 1 ) 一标号问题是n p - 完全的若缸p + 2 ，则l ( p ，1 ) 一标号问题 是多项式可决定的在近似算法方面，由嘲给出一个i y ( g ) 1 ) + o ( 、i y ( g ) i ) 一 近似算法 l ( 1 ，1 ) 标号图g 的l ( 1 ，1 ) 标号等价于g 的平方图g 2 的染色，易见 a l 。1 ( g ) = x ( g 2 ) 一1 定义，( ( g ) ，们= m a x 仅( g 2 ) l g 具有最大度( g ) 和围长 g 因为g 2 的最大度至多为( g ) + ( g ) ( ( g ) 一1 ) = 2 ( g ) ，从而对于任意9 ， ，( ( g ) ，9 ) 2 ( g ) + l ( 1 ) 对于( g ) = 2 和g 5 ，g = 既时使得( 1 ) 中等号成立对于( g ) = 3 和g 5 ，g 为p e t 哪蛐图时使得等号成立对于( g ) = 7 和g 5 ，g 为 h o 鼢m s i n 西e t o n 图时。见【1 0 1 ，使得等号成立由b r o o k s 定理【l l ，1 2 1 ，只有 当g 5 且存在直径为2 具有顶点效为2 ( g ) + l 的( g ) 正则图等号才 能成立在f l o 作者证明如果这样的图g 存在，那么( g ) 2 ，3 ，7 ，5 7 然 而，对于( g ) = 5 7 时还是一个未解决问题a l o n 和m 0 h 耻 1 3 】证明t( i ) 存 在一个函数( ( g ) ) ，当( g ) 。时e ( ( g ) ) + 。o ，使得对于所有口6 ， 有( 1 一( ( g ) ) ) 2 ( g ) ，( ( g ) ，们s 2 ( g ) + 1 ( i i ) 存在两个正常数c 1 和c 2 使得 4 对于任意( g ) 2 和9 7 ，则 c t 器 6 为整数其它未介绍的符号，术语在文献 1 1 ，1 2 】中找到 定义1 3 1 【1 2 】图g 的线圈l ( g ) 是以e ( g ) 为顶点集合的图。其中两个顶点 相邻当且仅当它们在g 中是相邻边 定义1 3 2 【1 2 】图g 的平方图g 2 是以v ( g ) 为顶点集合的图，其中两个顶 点u ，v 相邻当且仅当1 d g ( u ，口) 2 定义1 3 3 【l l ，1 2 】图g 的正常顶点染色是映射盯：y ( g ) + 1 ，2 ， 使 得任意相邻顶点u ，v 有盯( 让) 盯( 口) 图g 的色数x ( g ) 是最小的整数k 使得g 具有k - 顶点染色 定义1 3 4 【1 l 1 图g 的正常缸边染色是映射口：e ( g ) l ，2 ，惫) 使得 任意相邻边e ，f 有盯( e ) 盯( ，) 图g 的边色数x 7 ( g ) 是最小的整数k 使得g 具 有k - 边染色 定义1 3 5 m图g 的b 强边染色是正常如边染色，使得没有边相 邻于具有相同颜色的两条边如果g 具有k - 强边一染色那么称g 是舡强递 一可染的图g 的强边色数s ( g ) 是最小的整敦k 使得g 是k _ 强边一可染的 ( 三) 、基本概念和符号 定义1 3 6 【1 2 给g 的每个顶点口分配一个颜色列表l ( v ) ，g 的l 一染色 是正常顶点染色盯，使得任意 y ( g ) ，口( ) l ( 口) 若g 存在l 染色，那么称 g 为l 可染的如果对于任意给定的列表l ，它满足任意口，有 l ( 口) l = ，g 都 为l 可染的，那么称g 为k _ 可选择的g 的选择数( 或列表一色数) 弛( g ) 是最 小的整数k 使得g 是k 可选择的 显然，每个k - 可选择图是k 可染的( 考虑分配列表l ( ) = 1 ，2 ，计，任 意 y ( g ) ) 因此( g ) x ( g ) 然而，存在图g 使得x l ( g ) x ( g ) 。事实上， 对于任意整数k ，存在二部图g ，使得( g ) ，见 1 2 】类似的，可以定义g 的边列表分配l ，o 边。染色，k 边一可染的，k - 边可选择的，边一选择数 “( g ) ，l 一强边一染色，l 一强边一可染的，k _ 强边一可选择的，强边一选择数s 刈( g ) h a l l 定理1 3 1 【1 1 ，1 2 】设a 1 ，a 2 ，a 。是集合s 的m 个子集，子集族a = ( a l ，a 2 ，a 。) 的一个相异代表系( s d r ) 是指s 的一个子集合 n 1 ，口2 ，o 。) ， 满足( 1 ) 啦a ，i 从而矽具有s d r ，扩展盯到g 若b 成立不妨设如l ，0 2 ，口4 x 令口( n 4 ) = 盯( e 1 ) = 口l ( 0 4 ) n ( e 1 ) ， 仃( 。2 ) = 仃( e 4 ) = 卢三7 ( 2 ) nl ( e 4 ) a ) ，盯( 。1 ) = 仃( e 3 ) = 7 三7 ( 口1 ) nl 7 ( e 3 ) 口，声) 类似于以上，依次给未染色边啦，b 3 ，6 4 ，口5 进行贪婪l 广强边一染色因为当给每 一条边e 进行染色时，n ( e ) 中至少有三条边还未染色，因此】f ( e ) 1 2 1 令 矿( e ) 三( e ) f ( e ) 然后依次给边魄加1 ，b 2 进行l 强边一染色，注意每一条边 e ，( e ) 中有边e 5 ，e 2 还未染色，且具有两条边具有同色，从而 f ( e ) 1 2 1 ，令 l ”= ，( e ) e e 2 ，e 5 ) ) ，( e ) = ( e ) 黯( e ) 其中l ( e 2 ) i 2 ，i 工5 ) i 2 从 而l ”具有s d r ，扩展盯到g 若l x f = 1 2 则ju 。x ( 8 ) 1 1 从而任意o ，dnx ，e ( g ) nx 有i 三7 ( 。) n 五( 可) = f 三( z ) f + f 三) 一 三7 ( z ) u 五7 ( ) f 3 ，f ( 。) n 三7 ( ，) f = 1 ( z ) + l ，( ，) 1 一l 7 ( z ) u l 7 ( ，) 1 6 若2 冬1 xn e ( e ) l 4 ，则i x n d l 8 讨论 相同于情形8 l x i 1 0 即可。若l x n e ( g ) i = 5 则i x n d i = 7 ，l d x l = 3 从而 存在 龟：8 i + 1 ，8 m ) 冬x ，对于某个i 【l ，剐成立讨论相同于以上情形i x i = 1 l 中子情形( ) 中a 情形即可 若l x = 1 3 则 u 。x 二( e ) 1 2 从而任意。，f dn x ，e ( g ) nx 有 f ( z ) nl ，( 可) = l 7 ( z ) l + ( 二) 、( g ) = 4 时图的列表强边染色1 5 l 上7 ( 可) i 一 三( 。) u 三( 可) f 2 i 上7 ( z ) n 三( ，) l = l ( z ) j + l ( ，) i 一| l ( 。) u l 7 ( ，) l 5 若 l x n e ( g ) l = 3 ，则l x n d l = 1 0 设e 1 x 选取不同边o ，c d 2 ，b ：d d h ，d 4 使得d g ( o ，6 ) 3 ，d g ( c ，d ) 3 ，d g ( e 1 ，厂) 3 令盯( o ) = 盯( 6 ) = l ( o ) n 7 f 6 ) ， 仃( c ) = 盯( d ) = p l 7 ( c ) nl 7 ( d ) ( 。) ，仃( e 1 ) = 盯( ，) 一7 l 7 ( e 1 ) n ( ，) q ，卢) 这样以下讨论类似于情形i x i = 1 1 中( i ) 情形，g 是l 一强边一可染的若 i xne ( c ) l = 4 ，则 xnd l = 9 讨论类似于情形l x l = 1 1 中( i ) 情形即可 若i x i = 1 4 则iu 。xl 7 ( e ) i 1 3 从而任意g ，g _ dnx ，e l 主l 髻剐 靴；蘩! 型i 妻墓；! g ；一i 篓i 差! l 莲! 莹l 呈i | ；的i = i 誊主；罂i ! 羹；! 璧i 蜀l 蠹蕈：i 而；一 曷l 萋；l 簦i 塑；i 墓l i l 耋；! 焉；摹i l 饕菱! 矗| 蛐量登；蜒j ； 一* ：鞫i 蠹i 囊! 一；g 嚣l 篓馐蓁譬i i ? j ：? i l 萋圈，薅霸蒜羡莓誊隘噬 且u = - v 定义4 1 5 俐若图g 仅含有一个圈，则称g 为唯一圈图若图g 的每个块 或者为一条边或者为一个罔，则称g 为仙人掌图 引理4 1 1 【3 】如果g 存在一个主要顶点，使得它的所有邻点都是主要的，那么 ( g ) 并裟纂勰 引理4 l 2 对于任意的正整数p 口和南，满足p 女，口j ，那么 a m ( g ) a 幻( g ) 引理4 1 3 【3 1令g n 为圈，以下成立 ( 1 ) 若p = 1 ， f2 ，若n 兰o ( m o 粥) ， 则a 1 1 ( g ) = 3 ，若n o ( m o d 3 ) 且n 5 i4 ，若n = 5 ( 2 ) 若p 一2 ，则a 2 ，l ( 瓯) = 4 ( 3 ) 若p 3 舭“咖陵强篡 x 浙江师范大学硕士论文：第二章图的强边染色 引理2 2 6 令t 为树( 如上所叙，下同) ，设l 为t 的任意一个边列表分 配使得 ( 1 ) 1 三( 勖) = 1 3 ：i 1 ：4 】 ( 2 ) 三( 啦) 1 = i 工( 乱) i = l 三( q ) f = 4 ，i ( 1 ，4 若盯为d 中某些边的l 强边一染色，满足以下条件之一，那么a 可以扩展到t 的一个l 强边一染色 a 1 ：若d 中存在两对分离边 o 6 ， c ，d ) 使得盯( n ) = 仃( 6 ) 三( n ) nl ( 6 ) ， 仃( c ) = 伊( d ) l ( c ) n l ( d ) ，且仃( n ) 盯( c ) a 2 ：若d 中存在三条分离边血，6 ，c 使得仃( o ) = 口( 6 ) = 盯( c ) l ( 口) n l ( 6 ) n 三( c ) a 3 ：若d 中存在两条分离边o ，6 使得口( o ) = 盯( 6 ) l ( n ) n l ( 6 ) ，以及另外一 条边c d ，使得a ( c ) l ( c ) l ( e 。) ，对于某个i 1 ，4 】成立，且盯( 口) a ( c ) 证明：若矿满足a 1 ，不妨设 。，吩= 吼，口2 ) 只须考虑以下三种情形即可 i 、设 c ，d ) = 伯1 ，6 2 ) 、设 c ，d = 如，6 3 ) 、设 c ，d ) = b ，扫4 ) 若i 成立，设仃( 0 1 ) = 盯( n 2 ) = a l ( 0 1 ) n 三( 0 2 ) ，仃( 6 1 ) = = 盯( 6 2 ) = p l ( b ) nl ( b 2 ) ，且卢令l ( c 1 ) = l ( c 1 ) q ，卢) ，三7 ( c 2 ) = l ( c 2 ) 口，卢) ，l ( 岛) = 三( ) ，厣 ，i 1 ，4 ，三( e ) = 己( e ) ，e p 3nd 4 ，则 三( c 1 ) 2 ，i ( c 2 ) j 2 ， l ，( e t ) l 1 1 ，1 l ( e ) l = 4 有以下断言 断言：令t 为树， e ( t 7 ) = e ( t ) 0 1 ，口2 ，6 1 ，b 2 ) 且i 二7 ( c ) i = i l ( c 2 ) i = 2 ，i l 7 ( e 。) l = 1 1 ，i 1 ，4 ，i l ( e ) l = 4 ，e d 3nd 4 若令= l ( e ) l e e ( r ) ) ，则 r 是一强边一可染的 证明：若三7 具有s d r ，断言成立若三不具有s d r ，那么由h a l l 定理， 知存在xse ( t 气使得iu 。e xl 7 ( e ) l i x l 设x 为使得l x l iu 。e xl ，( e ) i 具有最大值的子集若xn 彤= 0 首先给x 中边进行贪婪l 一强边一染色， 设盯7 为x 中边的l 7 一强边一染色令= f ( e ) i e e ( r ) x ，其中( e ) = l ，( e ) b ，( e ) 注意到若存在e ( d 3 u d 4 u c 1 ，c 2 ) ) x ，显然( e ) o 若e w 则 f b “e ) l 8 ，( e ) d 若扩具有s d r ，那么通过令盯，( e ) 矽( e ) ，e e ( r ) x 扩展盯7 到r 若不具有s dr ) 那么由h a u 定理，知存在x e ( t ，) x ， 使得ju 。x ，( e ) l 逝婆竖蕉太学硕士论文：第二章图的强边染色 证明：设l 为g 的任意一个边列表分配使得任意e e ( g ) ，l l ( e ) i = 1 1 对 予任意e e ( g ) ，f ( e ) i 1 2 令c 为g 的任意4 圈，e ( a ) = 龟k 1 ，4 边 口t 相邻于边e 一，岛( 下标取模4 ，下同) 顶点孔为边吼不在c 上的端点如图2 5 方便起见，令d = e t ：吼卜【1 ，4 ) 由引理2 3 1 ，g v ( c ) 是l 强边一可染 的由g ( g ) = 4 ，故。：与o 。l 不能相邻 图2 5 若。1 与。3 重合那么给。1 ，0 2 ，a 3 ，。4 进行贪婪l 一强边一染色因为任意 啦，i f ( o t ) i 8 然后令= 三，( e 。) 卜 1 ，4 ，其中l ，( e t ) = l ( 既) f ( e t ) 注意到每 条边e 。，有| ( 黾) i 1 0 ，l f ( 如) l 1 0 一3 = 7 ，i 上( e i ) i 4 从而l 具有s d r ，通 过令盯( e i ) ( 勖) 扩展盯到g 若。2 与z 4 重合，那么类似处理从而以下假设 翰卜 1 ，4 】) 中不存在重合顶点 若d g ( o l ，。3 ) 3 即z 1 与黝不重合且0 1 茹3ge ( g ) 令l 7 = l ，( e ) 1 e d ) ，其 中l 7 ( e ) = l ( e ) f ( e ) 注意到若e e ( c r ) ，贝l | f ( e ) j 4 ，| 工7 ( e ) i = j l ( e ) f ( e ) i 7 若e 0 1 ，0 2 ，n 3 ，0 4 ) ，则| f ( e ) i 6 ，因此i ( e ) l25 若l 7 具有s d r ，那么通 过令盯( e ) 三，( e ) 扩展口到g 若l 7 不具有s d r ，那么由h a u 的定理，知存在 x d ，使得iu 。e xl ”) i i x | 设x d 为使得i x l lu 。xl ，( e ) i 具有最大值 的子集从而假设xn e ( g ) 0 因为若xn e ( g ) = 0 首先给x 中边进行贪婪 三7 一强边一染色令7 = l ”旧d x ，l ”( e ) = ( e ) f ( e ) 若具有s d r ， 那么通过令盯( e ) ( e ) ，e d x 扩展盯到g 若l “不具有s d r ，那么由h 甜l 的定理，知存在x 7 d x ，使得fu 。x ，( e ) l | x i lu 。xl ，( e ) 1 与 x 选取矛盾从而l x l = 8 ，lu 。xf ( e ) i 7 因此二7 ( o ) n ( 口3 ) 口令盯( 0 1 ) = 盯( 0 3 ) = o l ( n - ) nl 7 ( 0 3 ) 从而若令l ”= 工”( e ) = l 7 ( e ) 口) i e d 口t ，n 3 ， 则i ( 白) l 6 t 1 ，4 】| ( 。2 ) l 4 ，l ( n 4 ) i 4 因此l ”具有s d r ，通过令 盯( e ) ( e ) ，e d 0 1 ，0 3 ) 扩展盯到g ，若d g ( n 2 ，0 4 ) 3 类似处理即可以下 假设d g ( o l ，d 3 ) = 2 ，d g ( ( 匕，6 阻) = 2 ! 三! ：垒l 垡三! 堕图煎型塞：塑塑：塑鱼 2 1 若d o ( n 1 ，3 ) = ：2 ，d g ( 。2 ，n 4 ) = 2 即。1 2 3 凹( g ) ，z 2 0 4 e f g ) 若 z t 。e ( g ) 令= l ( e ) 1 e d ) ，其中l 7 ( e ) = l ( e ) f ( e ) 注意到l f ( e ，) 1 3 ，l 三( e - ) l 8 若e e ( g ) e 1 ) ，则l l 7 ( e ) l 7 若e n t l i 1 ，4 ) ，则l 己7 ( e ) l 5 因此l 7 具有s d r ，那么通过令口( e ) 三，( e ) 扩展盯到g 若。2 2 3 e ( g ) 或 1 茁4 e ( g ) 或z 3 茁4 e ( g ) 类似处理即可以下假设勘茁件lge ( g ) ，t 【1 ，4 设 ，3 分别为n 1 ，0 3 的邻边， ，1 。1 乳，3 z 1 。3 注意到d g ( ，e 2 ) 3 ， d g ( ，3 ，e 1 ) 23 ，首先删掉边 ，3 的原有染色令l = l ，( e ) i e d u ，1 ，3 ) ， 其中l k ) = l ( e ) f ( e ) 那么若e e ( g ) ，则i f ( e ) i 3 ， l 沁) i 芝8 若e o 。| i 1 ，4 】) ，贝0i f ( e ) f 5 ，l ( e ) l 6 且i f ( ) 7 ， l ( ) | 4 ，i f ( ，3 ) l 7 l 7 ( ，3 ) l 4 若l 7 具有s d r ，那么扩展仃到g 若l 7 不具有s d r ，那么由h a u 定理，知存在x 口u ，1 ：，3 ) ，使得iu e x 三，( e ) | i x i 设x du ，3 ) 为使得l x l iu 。x 三如) l 具有最大值的子集类似的，假设xne ( a ) 0 从 而9 | x i l o ，iu 。xl ，( e ) 9 因此 ，1 ，e 2 ) x 或 ，3 ，e 1 ) x 不妨设 ，3 ，e t ) x 贝0l 7 ( e ) n 工7 ( ，3 ) 0 令盯( ，3 ) = 盯( e ，) = 口l ( e 1 ) n 三( ，3 ) 令 l “= l ”( 8 ) = f ( e ) q ) j e ( d e 1 ) ) u ，1 ) ) ，则1 l ”( e t ) 1 7 ，i 【2 ，啕，1 l “( o 。) i 5 ，t f 1 ，4 ， ( ) | 3 若具有s d r ，那么扩展口到g 若l ”不具有s dr j 那么由h 出l 定理，知存在x 7 ( d e 1 ) ) u ( ，使得u 。x ，( e ) l l x 斗设 x 7 ( d e 1 ) ) u ( ，1 ) ，为使得l x _ 一lu 。x ，( e ) l 具有最大值的子集类似的，假 设x 7 n e 2 ，e 3 ，e 4 ) 0 从而l x ，| = 8 ，i u 。x ，( e ) l 7 因此( ，1 ) n l ( e 2 ) 0 令 口( ，1 ) = 盯( e z ) = 卢三”( ) n 7 ( e 2 ) 若令l = l ”7 ( e ) = 7 ( e ) 卢) i e 吼k 【l ，4 ) u e 3 ，e 4 ) ) ，则j l ”拈。) l 6 ，t 3 ，4 】，i 三( n 。) l 4 因此l 具有s d r ，通过令 盯( e ) l ( e ) ，e o 。i i 1 ，4 u e 3 ，e 4 ) 扩展盯至0g 引理2 3 4 令g 为3 正则图，若9 ( g ) = 5 ，则s x ，( g ) 1 l 证明：设l 为g 的任意一个边列表分配使得任意e e ( g ) ，l l ( e ) i = 1 1 令 c 为g 的任意5 一圈，e ( g ) = e e 悖【1 ，5 】) 边o 。相邻于边龟山e ( 下标取模5 ， 下同) 顶点观为边鳓不在c 上的端点方便起见，令d = o i k 1 ，5 任意 e e ( g ) ，则| ( e ) i 曼1 2 由g ( g ) 一5 ，贝0d g ( 。t ，茁。+ 1 ) 2 ，顶点。与z 件2 不能重 合，d g ( o t ，e t + 2 ) 3 ，i 1 ，5 】由引理2 3 1 ，g v ( c ) 存在i 广强边一染色盯令l 7 = l ，( e ) i e due ( g ) ) ， 其中l 7 ( e ) = 工( e ) f ( e ) 若e e ( g ) ，贝0l l ( e ) l = i l ( e ) f ( e ) l 7 若e d ，贝0 l l ，( e ) i 5 若l 7 具有s d r ，那么通过令盯( e ) l ，( e ) 扩展盯到g 若上不具 有s d r ，那么由h 血l 的定理，知存在x due ( a ) ，使得1u 。x 工7 ( e ) i 4 从而j 乙具有s dr 1 通过令口( 岛) l ( e 。) 扩展口到g 情形2 ：若d 中存在唯一两对相邻边 。，6 ) j ( c ，田使得每一对相邻边共同 关联于不在c 上的同一个顶点只须讨论两种情形， a ：若f 。，讣cd 】u d 3 i c ，田d 2ud 4 b ：若 8 ，b 2 与0 4 重合注意到每个e t ，有 ( e ；) is2 1 a 1：若d g ( b 2 ，6 4 ) = 2 ，即2 玑e ( g ) 设边驰破，9 4 疆为边6 4 的不同于现玑的另外 两条邻边，边轨照，9 2 扼为边如的不同于驰玑的另外两条邻边由引理2 2 ，1，gy(g)存在21一强边一染色a首先给d中边进行贪婪21一强边一染色然后令l = l(e)h1，4m其中l(岛)=【l，21jf(e1)因为(岛)中存在c上三条边还未被 染色，故i f ( 岛) j 2 l 一3 = 1 8 ，f l ( 日) l 3 ，若l 上( e 1 ) = l ( e 4 ) i = 3 ，则i f( e ) i = f f ( e t ) | = 1 8 由于p ( 玑破) ，盯( 弧龋) ) n 盯( 垅如) ，盯( 耽碡) ) = 0 ，且 a (驰j)，一(弧衍)f(e4)，a(。i)，a(啦垢)f(e。)，a(e)11d。(e，e4)2 ，e g 口4 矾，9 4 嬷) ) = 口( e ) i l d g ( e ，e - ) s 2 ，eg 2 旌，忱p ；) ) ，因此l ( e 1 ) l ( e 4 ) ，i 二( e 1 ) u 三( e 4 ) i 4 从而l 具有s d r ，通过令( e 1 ) l ( e i ) 扩展盯到g a 2 ： 若如( 6 2 ，虬) 3 ，则啦驵ge ( g ) ，设边玑班，讥睫，矾馥为边6 4 的另外三条 邻边，边”2 9 i ，f 2 旌，垅旌为边6 2 的另外三条邻边由引理2 ，2 1 及引理2 4 2 ，g y ( g ) + 驰9 4 存在2 1 一强边一染色口首先给d 中边进行贪婪2 1 强边染色 然后令=(l(包m儿41)，其中l(如)=【1，21】f)则5l(龟)i3。 若l (e1)=fl(e4)i=3，则if(e1)i=1f(e4)i=18类似于情形21，同样有l (e 1 ) l ( e 4 ) ，j l ( e 1 ) u l ( e 4 ) f 4 因为在g y ( g ) 中通过连接抛驰使得p ( 乳蠡) ，a ( 弧谵) ，一( 弧蠊) ) n p ( f 2 醍) ，( 。谚) ，( 2 谚) ) = 0 从而三具有s d r ，通过令盯 ( e 1 ) l ( 龟) 扩展口到g 若b 成 立不妨设 口，6 ) = 。i ，n 3 ， c ，毋= d l ，b ，即顶点z t 与z 3 重舍，- 与珈重合注意到若e d lu d 3 有 ( e ) l 2 1 若存在 e d 2 ，d 4 使得d g ( e ，) 3 设( e ， = ( 口