（运筹学与控制论专业论文）混合超图的染色理论.pdf

s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 混合超图的染色理论 刁科凤 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) ( 指导教师：刘桂真教授) 中文摘要 超图是有限集合的子集系统，是最基本的离散结构设x = 。2 ，。) 是一个有限集合，s = s x ：l s l 2 ) 是x 的一个子集族，称二元系统 7 = ( x ，s ) 是集合x 上的一个超图，s s 称为超边超图的染色是对该有限 集合的顶点进行染色，使得每一超边中的点不能全部染同一种颜色超图的染 色理论解决的是根据一定的约束条件，将一个目标集分解为若干子集的问题 显然超图乱的最大染色数等于其顶点的个数，因此超圈的染色理论是最小顶点 染色理论超图w 的最小染色数称为该超图的色数超图的染色理论在地图染 色、工作排序等领域有重要的应用 自然地，我们考虑其对偶问题，即在超图的染色中。某些超边中的点不能 染完全不同的颜色v v o l o s h i n 将这种超边称为g 一超边，相应地称原来的超 边为d 一超边，从而引进了混合超图的概念 设x = 。l ，z 2 ，。) 是一有限集合，c = g x ：1 c l 2 ) 和d = d x ：i d i 2 ) 是x 的两个子集族，称三元系统w = ( x ，c ，d ) 为x 上的一个混合 超图，c c 称为c 一超边，d d 称为d 一超边c 或口可以是空集，而且 二者可以有交集特别地，若c = 0 ，则称7 = ( x ，d ) 为一d 一超图，同样，若 口= 0 ，则称w = ( x ，c ) 为一口超图，若c = 口，则称咒为b i _ 超图或b 一超图 两种超边的区别主要体现在染色要求上 混合超图刊= ( x ，c ，口) 的一个t 色严格染色指的是对其顶点进行染色，使 得每一g 一超边至少有两个点染相同的颜色，每一d 一超边至少有两个点染不同 的颜色，且所用的颜色数为t 这里c 表示“c o m m o n ”，d 表示“d i f f e r e n t ” 显然对于混合超图，最小染色数和最大染色数都有重要的意义混合超图 w 的用颜色最少的严格染色所用的颜色数称为张的下色数，记为x ) ，用颜色 最多的严格染色所用的颜色数称为w 的上色数，记为趸) 不难看出传统超图是混合超图的特殊情形，即d 一超图因此混合超图的 染色理论有重要的理论意义，而且混合混合超图的染色理论比传统超图的染色 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 理论有更丰富的内容同样该理论也有很强的实际背景如 如能源供应问题：有一组能源，所有能源都可在任何单位时间内开通且工 作时间都为一个单位时间但有些能源不能完全同时开通，而有些能源又不能 在完全不同的时间开通第一种类型的能源组构成d 一超边，第二种类型的能源 组构成c 一超边，而对应的混合超图的上色数即为该缀能源的最长供能时间 工作排序问题：有n 项工作，每项工作可在任何单位时间内完成有一些 工作由于使用同一种资源，因而不能同时开始，而由于技术上的原因，有些工 作又必须同时开始第一种类型的工作组构成d 一超边，第二种类型的工作组构 成c 一超边，对应混合超图的下色数就是完成这n 项工作所需的最短时间，需 要注意的是下色数与c - 超边是有关的 该理论还可应用于平行计算、数据库管理及分子生物学等领域它将会引 起许多数学工作者，特别是离散数学界、组合最优化界、运筹学界、计算机科 学界、分子生物学界及相关工业和商业界工作者的极大兴趣 混合超图的染色问题是1 9 9 2 年提出来的，正式发表的第一篇文章( i t 4 ) 于 1 9 9 5 年刊登在“d i s c r e t em a t h e m a t i c s ”该理论是国际上比较新的一个课题，有 很多的问题等待我们去解决目前对该理论的研究主要集中在以下几个方面： 可染色性；唯一染色混合超图；混合超图的g 一完美性；块设计的染色；c - 超 图的染色；混合超图的整数规划形式与分数染色；平面混合超图的染色等本 文我们主要研究c 一超图的染色、块设计的染色及混合超图的g 一完美性等全 文共分五章 第一章绪论，介绍了混合超图染色问题产生的理论与实际背景，常用术语 和符号，以及本文的结构及主要内容 第二章主要研究c 一超图的染色问题可以肯定c 一超图的染色理论同样 有丰富的内容对g 一超图的染色，重要问题之一是研究其上色数我们首先对 给定c 一超图的上色数的界进行了研究，然后讨论了g - 超图上色数等于t 的条 件本部分的主要工作是引入了g 一超图的一分解及相应的点对图的概念，得 到了g 一超图上色数等于t 的两个充要条件 结论l 设孔= ( x ，c ) 是一个g 一超图，则又( 确= t 的充要条件是( 1 y m 有t 一 分解；( 2 ) 每一t 一分解丸l = ( x ，x i ，c i ) ，9 2 = ( x ，x 2 ，c 2 ) ，w f _ ( x ，x t ，c t ) 满足 对任意i l ，2 ，t ，或者l 五i = 1 ，或者对置的任意分解x i = x i lu 置2 都存 在c 矗使j c n 五 2 ，s 1 ，i l ，i + 1 ，0 ，并且j g n 粕i = l ，j = l ，2 结论2 设州= ( x ，c ) 是一个e 一超图，则x ) = # 的充要条件是( 1 ) 9 有卜 分解；( 2 ) 每一t 一分解他1 = ( x ，x 1 ，c 1 ) ，礼2 = ( x ，恐，c 2 ) ，丸t = ( x ，x t ，c t ) ，对 应的点对图g w ，g 赳。，g w 。都连通 n s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 该结论开拓性地将混合超图的染色理论与普通图论中图的连通性结合在一 起，开辟了研究混合超图染色理论的一条新的有效途径利用该结论我们讨论 了一致c 一超图的最小边数与最小上色数之间的关系，得到了上色数最小的r 一 致c 一超图的边数的一个下界 结论3 设丸= ( x ，c ) 是一r 一致c 一超图，满足1 x i = n 且甏) = r l ， 则有 l c i 型坚尘尘三崞坠业坠三盟1 本部分我们得到的另一个重要结论是证明了结论3 中给出的下界当r = 3 时是可以达到的 结论4 存在满足又( 咒。) = 2 ，1 x 。1 = n 且l c n l = f 学1 的3 一致c 一超图 “。= ( x 。，厶) 本章的最后我们研究了g 一超图的笛卡儿积的染色问题得到的主要结果 如下： 结论5 设w = ( x ，a ) 和9 = ( y ，召) 是两个r 一致口超图并满足1 x i = i y = n ，趸( w ) = 又( 0 ) = r 一1 令n 一( r 一2 ) = m ，k = 【票j ，贝0 有 又( “g ) = n p 一2 ) + k 第三章研究的是块设计的染色问题块设计在组合最优化和计算机科学等方 面有重要的地位，可以肯定地说将块设计看作混合超图，一定会得到许多很好的 性质我们主要讨论斯泰勒三元系( s t s ) 和四元系( s q s ) 的染色问题l m i l a z z o ， z s t u z a 和v v o l o s h i n 等人首先将斯泰勒系统看作混合超图并对此做了大量的 工作他们这方面的首篇文章( 5 0 】) 于1 9 9 7 年刊登在“d i s c r e t em a t h e m a t i c s ”， 文中证明了：一个c s t s ( n ) 若满足n 2 一1 ，则有夏k = 【t 0 9 2 ( n + 1 ) j ，并且 还证明了当n = 2 k 一1 时该上界可以达到因而在文章的最后作者提出了如下 的问题： 问题( l m i l a z z o ，z s 弛a 【5 0 ) 当n 2 一l 时c s t s ( n ) 的上色数的上界 1 0 9 2 ( 7 2 + 1 ) i 的紧性如何? 我们的主要工作是对以上问题进行讨论并最后结果彻底解决了该问题 结论6 对所有可能的t l 都存在上色数为l l 0 9 2 ( n + 1 ) j 的c s t s ( n ) 对s t s 染色讨论的重要方法之一是构造法l m i l a z z o ，z s r u z a 和v v o l o s h i n 等人给出了s t s 的2 倍加1 构造法，赵平( 7 9 1 ) 给出了s t s 的3 倍构造 法我们在讨论的过程中，所做的另一重要工作是得到了另外的三种构造s t s 的方法，它们分别是s t s 的2 倍加7 构造法、4 倍加3 构造法及2 倍加3 构造 法这几种构造法将会对块设计的研究很有帮助 1 l l s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 第四章是关于几类特殊混合超图的染色，特殊混合超图在混合超图的染色 理论中有比较好的性质我们首先讨论的是完全不规则口超图的染色问题 我们知道任一图中至少有两个点的度数相同，但该结论对超图不成立，即存在 各点度数都不同的超图，这样的超图称为完全不规则超图若一个混合超图州 是另一个混合超图丸的导出子超图，我们也说可嵌入到瓤中对于新的混 合超图染色理论，自然地考虑嵌入过程中所涉及的两个混合超图的上色数的关 系我们最先开始讨论该问题并得到了如下的结论 结论7 任一3 一致c 一超图都可嵌入到一个3 一致完全不规则3 一致c 一超 图中并保持上色数不变 接下来讨论的是混合超图的c 一完美性问题我们知道一个图的团数是该 图的色数的一个下界，而传统超图中很难找到性质类似团的子图在混合超图 的染色理论中c 一稳定集的性质类似于团的性质，容易证明趸) a ( w c ) 对任 意混合超图丸都成立。其中对一个混合超图a ( 7 v c ) 是斜的稳定数 w 若 贾( w ) = 口( 饨1 ) 对w 的任意子超图硝都成立，则称w 为c 一完美混合超图v v o l o s h i n 在他的第一篇文章( 【7 4 】) 中就讨论了该问题，文中提出了一个猜想：混 合超图w 是c 一完美的充要条件是n 没有导出子超图是c 一单曼或g 一摆线 但文献【3 8 】给出了该猜想的反例我们得到了c 一超图是c 。完美的一个充分条 件 本章的最后我们研究了区间混合超图的染色，混合区间超图在分子生物学 中有重要的应用e b u l g a r u 等人最先对混合区间超图的染色进行了研究，得 到的结果是：任一混合区间超图h 都满足x ( w ) = s ) ，其中s ( 咒) 是丸的筛数。 我们证明了该结论对3 一致混合区间超树也成立 结论8 任一3 一致混合区间超树州= ( x ，c ，d ) 都满足又( 咒) = x 卜- s ) ，其 中s ( n ) 是丸的筛数， 第五章我们简要介绍了混合超图染色理论其它方面的进展并列出了可供进 一步研究的问题，以期引起更多同行的兴趣，使更多的专家学者从事该理论的 研究 关键词：混合超图；严格染色；下色数；上色数 l v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n c o l o r i n gt h e o r y o fm i x e d h y p e r g r a p h s d i a ok e f e n g ( s c h o o lo fm a t h s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ) a b s t r a c t t h i sd i s s e r t a t i o nd i s c u s s e st h ec o l o r i n gt h e o r yo fm i x e d h y p e r g r a p h s w ek n o w t h a t ah y p e r g r a p hi sas y s t e mo fs u b s e t so faf i n i t es e t 、i ti st h em o s tb a s i cd i s c r e t es t r u c t u r e s l e tx = z l ，。2 ，一，z n ) b eaf i n i t es e ta n ds = ( s ：s x ，i s l 2 ) b eaf a m i l yo f s u b s e t so fx t h ep a i r 饨= ( x ，s ) i sc a l l e dah y p e r g r a p ho nx ，a n de v e r ys si sc a l l e d ah y p e r e d g e t h ep r o p e rc o l o r i n go fah y p e r g r a p hi sb a s e do nt h ef o l l o w i n gf u n d a m e n t a l r e s t r i c t i o n ：t oa s s i g na tl e a s tt w od i f f e r e n tc o l o r st ov e r t i c e si ne v e r yh y p e r e d g e i td e a l s w i t ht h ef u n d a m e n t a lp r o b l e mo f p a r t i t i o n i n gas e to fo b j e c t si n t oc l a s s e sa c c o r d i n gt o c e r t a i nr u l e s t h ec h r o m a t i cn u m b e ro fah y p e r g r a p hi st h em i n i m u mn u m b e ro fc o l o r s n e e d e dt oc o l o ri t sv e r t i c e sm e e t i n gt h i sr e q u i r e m e n t t h em a x i m u mn u m b e ro fc o l o r s m e e t i n g t h i sc o n s t r a i n ti st r i v i a l l ye q u a lt ot h en u m b e ro fv e r t i c e s t h e r e f o r e ，t h ec l a s s i c a l c o l o r i n gt h e o r yo fh y p e r g r a p h si st h et h e o r yo fm i n i m u mv e r t e xc o l o r i n g i ti sv e r yn a t u r a lt ot h i n ko f c o l o r i n gt h ev e r t i c e so fah y p e r g r a p hs u c ht h a ti ns o m e h y p e r e d g e sa tl e a s tt w ov e r t i c e sh a v et h es a l v ec o l o r i n1 9 9 5 ，v v o l o s h i ni n t r o d u c e dt h e n o t i o no fc - e d g e so fah y p e r g r a p h ，w h i c hi sa l s oas u b s e to ft h ev e r t e xs e t i nc o l o r i n ga h y p e r g r a p h ，a tl e a s tt w ov e r t i c e so fac e d g es h o u l db eg i v e nt h es a x a ec o l o r i no r d e r t od i s t i n g u i s ht h e s et w ok i n d so fh y p e r e d g e s ：w ec a l lt h eo l dk i n dh y p e r e d g e sd - e d g e 8 a h y p e r g r a p hw i t hb o t hf a m i l i e so fd - e d g e sa n dc - e d g e si s am i z e dh y p e r g r a p h w e d e n o t eam i x e dh y p e r g r a p hw i t hv e r t e xs e tx b y “= ( x ，c ，d ) ，w h e r eci s t h ef a m i l y o fg e d g e sa n d 口i st h ef a m i l yo fd e d g e s i nam i x e dh y p e r g r a p h7 = ( x ，c ，口) ， t h ef a m i l yo fc - e d g e sco rt h ef a m i l yo fd e d g e sd m a yb ee m p t ya n dt h e ym a yh a v e i n t e r s e c t i o n s p e c i a l l y , f o r am i x e dh y p e r g r a p h 州= ( x ，c ，口) i fc = 0 ，t h e n 科i s s i m p l yad - h y p e ，y r a p ha n di sd e n o t e d 两丸d = ( x ，口) ii fd = 0 ，t h e n i ss i m p l y 。 c h y p e r g r a p ha n d i sd e n o t e db y “c = ( x ，c ) ；i f c = 口，t h e n7 4i ss i m p l yab - h y p e r g r a p h t h ed i f f e r e n c eb e t w e e nc e d a e sa n dd e e si si nt h er e q u i r e m e n t si ndc o l o r i n g as t r i c tt - c o l o r i n go fam i x e d h y p e r g r a p h7 - 1 = ( x ，e ，d ) i sac o l o r i n go fi t sv e r t i c e s s u c ht h a te a c hc - e d g eh a sa tl e a s tt w ov e r t i c e sw i t hac o m m o n c o l o r ，e a c hd e d g eh a s a tl e a s tt w ov e r t i c e sw i t hd i f f e r e n tc o l o r sa n dt h en u m b e ro fu s e de o l o r si s e x a c t l yt ot v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n i nt h i sw a y ”c ”s t a n d sf o r c o m m o n c o l o ra n d ”d s t a n d sf o r ”d i f f e r e n t ”c o l o r s i nam i x e dh y p e r g r a p hi tm a k e ss e n s et oa s kf o rb o t ht h em i n i m u ma n dt h em a x i 。 m u mn u m b e r so fc o l o r sr e q u i r e df o ras t r i c tc o l o r i n g t h em a x i m u m ( m i n i m u m ) i n t e g e r tf o rw h i c ht h e r ee x i s t sas t r i c t t - c o l o r i n go fam i x e dh y p e r g r a p hw i sc a l l e dt h eu p p e r ( 1 0 w e r ) c h r o m a t i cn n m b e r o f 咒a n dd e n o t e db y 趸( 丸) ( x ( w ) ) t h ec l a s s i c a lc o l o r i n gt h e o r yo fh y p e r g r a p h sb e c o m e sa s p e c i a lc a s e ，i , e ，t h ec a s e o fm i x e dh y p e r g r a p h sw i t ho n l yd e d g e sa n dl o w e rc h r o m a t i cn u m b e r s w eb e h e v et h a t t h en e wc o l o r i n gt h e o r yw i l lh a v eb o t hi m p a c to nt h ec l a s s i c a lc o l o r i n gt h e o r ya n di t s o w nd i r e c t i o no ft h e o r e t i cd e v e l o p m e n t w ea l s ob e h e v et h a tt h en e wc o l o r i n gt h e o r yw i l l h a v ef a rm o r ei n f l u e n c ei np r a c t i c e sa n da p p l i c a t i o n st h a nt h ec l a s s i c a lc o l o r i n gt h e o r y t h e f o l l o w i n ga r et w oo ft h ep o t e n t i a la p p l i c a t i o n so ft h i sn e wt h e o r y s c h e d u l i n go fas y s t e mo fp o w e rs u p p l i e s ：a s s u m et h a tw eh a v eas e to f s o u r c e so fp o w e rs u p p l i e ss u c ht h a tt h ea c t i o nt i m eo fa n ys o u r c ei so n eu n i to ft i m e a n da l ls o u r c e sa c t i n gf o ra n yg i v e nu n i to ft i m es w i t c ho na n do 圩s y n c h r o n o u s l y ( 7 4 ) c o n s i d e rt h ef o l l o w i n gg e n e r a lc o n s t r a i n t so nt h e i rw o r k ：( 1 ) f o rs o m es u b s e t so ft h e s o u r c e so fp o w e r s u p p l i e s ，a tl e a s tt w os o u r c e sf r o mo n es u b s e tn e e dt oa c tf o rt h es a m e u n i to ft i m e ；a n d ( 2 ) f o rs o m eo t h e rs u b s e t so ft h es o u r c e so fp o w e rs u p p l i e s ，a tl e a s t t w os o u r c e sf r o mo n es u b s e tn e e dt oa c tf o rd i f f e r e n tu n i t so ft i m e t h es u b s e t si n ( 1 ) a r ec e d g e sa n dt h es u b s e t si n ( 2 ) a r ed e d g e s t h ec o l o r i n go ft h i sm i x e dh y p e r g r a p h i st h et i m es c h e d u l i n go ft h i ss y s t e mo fp o w e rs u p p l i e s t h eu p p e rc h r o m a t i cn u m b e ri s t h el o n g e s td u r a t i o no ft h es y s t e mi nw o r k i n gc o n d i t i o n j o bs c h e d u l i n g ：c o n s i d e ras e to fn j o b s l e tn ss u p p o s et h a te a c hj o bc a nb e e x e c u t e di no n eu n i to ft i m e ，s o m ej o b sc o m p l e t e dw i t ht h es a m er e s o u r c e si ft h e ya r e s c h e d u l e da tt h es a m et i m e s o m e j o b sn e e dt ob ee x e c u t e da tt h es a n l et i m ef o rn o ta t a l ld i s t i n c tu n i t so ft i m ei ng e n e r a lc a s e s ) b e c a u s eo fs o m e t e c h n o l o g i c a lc o n s i d e r a t i o n s t h es u b s e t so fj o b si nt h ef i r s tc a 。q ea x ed e d g e sa n dt h es u b s e t so fj o b si nt h es e c o n d c a s ea r ec - e d g e s t h e c o l o r i n go f t h i sm i x e dh y p e r g r a p hi st h ej o bs c h e d u l i n g t h el o w e r c h r o m a t i cn u m b e ro ft h i sm i x e dh y p e r g r a p hi st h em i n i m u mt i m er e q u i r e dt os c h e d u l e t h i ss e to f j o b s t h eu p p e rc h r o m a t i cn u m b e ro ft h i sm i x e dh y p e r g r a p hi st h em a x i m u m t i m er e q u i r e dt os c h e d u l et h i ss e to f j o b s ，i ti sb a di nt i m e c o n s i d e r a t i o n ，b u ti tm i g h tb e g o o di ns o m eo t h e r ( f o re x a m p l e ，r e s o u r c ea l l o c a t i o n ) c o n s i d e r a t i o n s i ti si m p o r t a n tt o n o t i c et h a tt h el o w e rc h r o m a t i cn u m b e ra l s od e p e n d s ( i tm i g h tb ei n c r e a s e d ) o nt h es e t o fc - e d g e s t h i sn e wt h e o r yc a na l s ob eu s e di np a r a l l e lc o m p u t i n g ，d a t a b a s em a n a g e m e n t ， s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n m o l e c u l a rb i o l o g y ，e t c i tw i l lb eo fi n t e r e s tt ob o t hp u r ea n da p p l i e dm a t h e m a t i c i a n s ， p a r t i c u l a r l yt h o s ei nt h ea r e a so fd i s c r e t em a t h e m a t i c s ，c o m b i n a t o r i a lo p t i m i z a t i o n ，o p - e r a t i o n sr e s e a r c h ，c o m p u t e rs c i e n c e ，s o f t w a r ee n g i n e e r i n g jm o l e c u l a rb i o l o g y ，a n dr e l a t e d b u s i n e s s e sa n di n d u s t r i e s v v o l o s h i ni n i t i a t e dt h i sn e w t h e o r yi n1 9 9 2 ，a n dt h ef i r s tp a p e r a b o u tt h i st h e o r y w a sp u b l i s h e di n ”d i s c r e t em a t h e m a t i c s ”i n1 9 9 5 t h e r ea r em a n y p r o b l e m sw a i t i n gf o r u st oi n v e s t i g a t e a tp r e s e n t ，t h es t u d yo nt h i st h e o r ya r em a i n l yo nt h ef o l l o w i n gd i r e c - t i o n s ：c o l o r a b i l i t y ；u n i q u e l yc o l o r a b l em i x e dh y p e r g r a p h s ；c - p e r f e c t n e s so fm i x e dh y p e r - - g r p h s ；c o l o r i n g so fb l o c kd e s i g n s ；c o l o r i n g so fc h y p e r g r a p h s ；i n t e g e rp r o g r a m m i n ga n d f r a c t i o n a lc o l o r i n g so fm i x e d h y p e r g r a p h s ；c o l o r i n g s o fp l a n a rm i x e d h y p e r g r a p h s ，e t c i n t h ed i s s e r t a t i o n ，w em a i n l yd i s c u s sc o l o r i n g so fc h y p e r g r a p h s ，c o l o r i n g so fs t e i n e rs y s t e r n s ，o rm o r eg e n e r a l l y ，c o l o r i n g so fb l o c kd e s i g n s ，c p e r f e c t n e s so fm i x e dh y p e r g r a p h s ， e t c w ed i v i d et h i st h e s i si n t of i v ec h a p t e r s c h a p t e r1 i st h ei n t r o d u c t i o na n dn o t a t i o n si l lt h i sc h a p t e rw ei n t r o d u c et h e t h e o r e t i c a la n dp r a c t i c a lb a c k g r o u n d so ft h i sn e wc o l o r i n gt h e o r y ，t h ed e f i n i t i o n sa n d t e r m i n o l o g i e s ，t h eo r g a n i z a t i o na n do u rm a i nr e s u l t s i nc h a p t e r2w ec o n c e n t r a t eo nc o l o r i n g so fc h y p e r g r a p h s w eh a v et h ef e e l i n g t h a tt h ec o l o r i n gt h e o r yo fc - h y p e r g r a p h sw i l lb ee q u a l l yr i c ha st h ec l a s s i c a lc o l o r i n g t h e o r yo fh y p e r g r a p h s t h ef i r s tc o n t r i b u t i o nw ed ot ot h i sa s p e c ti st h a gw ei n t r o d u c e t h en o t a t i o n so ft - s e p a r a t i o n sa n dt h ec o r r e s p o n d i n gp a i rg r a p h s ，a n dg e tt w on e c e s s a r y a n ds u f f i c i e n tc o n d i t i o n sf o rt h eu p p e rc h r o m a t i cn u m b e ro fac b y p e r g r a p ht ob ee q u a l t ot c o n c l u s i o n1 l e t7 4 = ( x ，c ) b ea c h y p e r g r a p h t h e nx ( w ) = 玎a n do n l y 玎( 1 ) 起h a s a t - s e p a r a t i o n ，a n d ( 2 ) i o ra n y t - s e p a r a t i o n ，7 4 1 = ( x ，x 1 ，c 1 ) “2 = ( x ，x 2 ，c 2 ) ，丸= ( x ，x ，c ) ，a n yi ( 1 ，2 ，- - ，t ，e i t h e rl x x i = x i lu 蕊2 ( x n n x i 2 = 0 ，x i j o 如rj w i t hi c f 3 x s i 2 ，d rs l ，i 1 i + 1 = 1o rs o t a n yn o n e m p t yp a r t i t i o no i = l ，2 ) ，t h e r ee z i s t sac - e 面ec 幺 吼a n d l c n 置j i = 1 o rj = l ，2 c o n c l u s i o n 2 。l e t 丸= ( x ，c ) b ea c h y p e r g r a p h t h e n 又( w ) = t 苛a n do n l y 玎( 1 ) nh a s t - s e p a r a t i o n sa n d ( 2 ) ，0 ra n yt - s e p a r a t i o n7 - l l = ( x ，x i ，c 1 ) ，丸z = ( x ，x 2 ，c 2 ) ，7 4 = ( x ，置，c t ) ，t ep a i rg r a p h s g w l ，g n 2 ，g n ca r ea l lc o n n e c t e d t h ea b o v er e s u l t si n i t i a t l yc o m b i n et h ec o l o r i n gt h e o r yo fm i x e d h y p e r g r a p h sw i t h s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n t h ec o n n e c t e d n e s so fc l a s s i c a lg r a p h s ，a n dt h e r e f o r eo p e n san e wa n de f f e c t i v ew a yt o s t u d yt h i sn e wt h e o r y u s i n gt h i sr e s u l tw ed i s c u s st h er e l a t i o n s h i pb e t w e e nt h es i z eo f m i n i m u mc e d g en u m b e r sa n dt h em i n i m u mu p p e rc h r o m a t i cn u m b e r so fu n i f o r mc - h y p e r g r a p h s a n dg e tal o w e r b o u n do ft h en u m b e ro fc e d g e so fr - u n i f o r mc h y p e r g r a p h s w i t hm i n i m u m u p p e rc h r o m a t i cn u m b e r c o n c l u s i o n3 l e t7 4 = ( x ，c ) b e 。nr - u n 咖r mc h y p e r g r a p hw i t h1 x f = n a n d 又( “) = r l2 唬e nw eh a v e j c l 2 n f 礼一f 礼陪 ! ! ! 坚二! n 1 f u r t h e r m o r e ，w ep r o v et h a tt h el o w e rb o u n dg i v e na b o v ei st h eb e s tp o s s i b l ef o rt h e c a s eo fr = 3 c o n c l u s i o n4 t h e r ee x i s t s 口3 - u n 咖丌nc h y p e r g r a p h = ( x n ，c n ) s u c ht h a t 趸n ) = 2 i l = na n d 恢l = f 业1 a tt h ee n do ft h i sc h a p t e rw ei n v e s t i g a t et h ec o l o r i n g so fc a r t e s i a np r o d u c to fg h y p e r g r a p h sa n d o b t a i nt h ef o l l o w i n gr e s u l t c o n c l u s i o n5 l e t7 4 = ( x a ) a n d9 = (