没有合适的资源?快使用搜索试试~ 我知道了~
∩∩可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)125-133www.elsevier.com/locate/entcs弦的奇最大度真圆弧图的色指数João Pedro W. Bernardia,1,3 Murilo V. G.da Silvaa,1,4André Luiz P.Guedesa,1,5 Leandro M.Zateskoa,b,1,2,6a巴西库里蒂巴巴拉那联邦大学信息学系b巴西查佩科南弗龙泰拉联邦大学摘要著名的D。1985年John- son的NP-完全性列仍然没有确定。Figueiredo、Meidanis和Mello的一个猜想在20世纪90年代后期公开,指出所有奇数最大度为Δ的弦图的色指数等于Δ。这个猜想已经在真区间图(真区间图的一个子类)上得到了证明。圆弧弦图)的奇数Δ的技术称为拉回。使用一种新的技术称为多拉回,我们证明了这一猜想成立的所有正常圆弧奇数Δ的弦图我们也相信,这种技术可以用于进一步的 结果对其他图类的边着色。保留字:回拉,圆弧,色度指数,边缘着色,弦1介绍圆弧图是一个圆上的有限组弧的相交图。如果没有一条弧恰当地包含另一条弧,则称该图是一个恰当的圆弧图。如果所有的弧都具有相同的长度,则该图称为单位圆弧图。虽然圆弧图类已经得到了很好的研究,但是除了最大度数为Δ的n-顶点真圆弧图所构成的子类之外,关于确定这类图的色指数的1 部分由CNPq支持(Proc. 428941/2016-8和硕士2部分由UFFS(Proc. 23205.001243/2016-30)。3winckler@ufpr.br4murilo@inf.ufpr.br5andre@inf.ufpr.br6leandro. uffs.edu.brhttps://doi.org/10.1016/j.entcs.2019.08.0121571-0661/© 2019作者。出版社:Elsevier B.V.这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。126JP W Bernardi等人/理论计算机科学电子笔记346(2019)125≤≥∩whichhaven/n1,Δ(mod(Δ+1))和大小为two的最大团,或whichhaven≠0(mod(Δ+1))[1].圆弧图形成区间图的超类。这两类图之间的一个重要区别是区间图有线性数量的最大团(在顶点数上),而圆弧图可能有指数数量的最大团。这可能暗示了为什么圆弧图的某些问题比区间图更难解决。例如,区间图的顶点着色是多项式的,而圆弧图的顶点着色是NP-困难的[4]。NP-hard边着色问题[5]是确定图的边着色所需的最小颜色量,使得没有两个相邻边接收相同的颜色的问题。 这个量称为色指数记为χJ(G)。通过定义,对任意图G,有χJ(G)Δ(G)。 著名的Vizing因此,满足χJ(G)= Δ(G)的图被称为第一类图,满足χJ(G)= Δ(G)+1的图被称为第二图。例如,一个完全图Kn是如果n是偶数,则为1类,否则为2类。我们解决了奇最大度的真圆弧弦(PCAC)图类中的边着色问题,即我们证明了所有这些图都是1类,并且我们的证明给出了这些图的多项式时间精确边着色算法。值得注意的是,即使对于形成PCAC图的一个重要子类的真区间图(在文献中通常称为独立图),该问题也仅针对具有奇数最大度Δ的图,通过称为拉回的技术解决[2]。 后来,这种技术也被用来解决所有奇数Δ的对偶弦图(形成区间图的超类)的边着色问题[3]。弦图色数的确定问题是著名的D。Johnson为了解决最大度为奇的PCAC图的问题,我们设计了一种新的技术称为多回调,我们怀疑它可以用于其他图形类。本文的组织如下:本节的剩余部分致力于一些初步的定义;在第2节中,我们讨论了[2]中介绍的回调函数,并给出了我们的多回调函数;然后,在第3节中,我们给出了我们使用第2节中介绍的多回调函数对PCAC图的结果。初步定义在本文中,图论定义遵循其在文献中的通常含义。特别地,G=(V(G),E(G))是一个图,V(G)是G的顶点集,E(G)是G的边集.边uv被称为与顶点u和v相关联,并且顶点u和v被称为邻居。顶点u的度,记为dG(u),是与顶点u关联的边的数量。G的最大度为Δ(G):= max{dG(u):u∈V(G)}.u的开邻域是集合NG(u):={v:uv∈E(G)}。u的闭邻域是集合JP W Bernardi等人/理论计算机科学电子笔记346(2019)125127BB{∈∈⊂{{\fn黑体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fscy66\2cHFFFFFF\3cH808080}{∈⊂⊂NG[u]:=NG(u)<${u}.若NG[u]=V(G),则称顶点u在G中是泛点. 如果V(H)V(G)和E(H)E(G),则称图H是G的子图. 设U为V(G)。由U诱导的G的子图定义为G[U]:=(U,uv E(G):u,v U)。设F E(G).由F诱导的G的子图定义为G[F]:=(u:uv Ffor somev V(G),F)。图的核心是子图由其最大度的顶点导出。图的半核是由最大度顶点及其邻居导出的子图。图G的k-边染色是指图G用k种颜色进行的真边染色,也就是说,图的边的颜色分配使得没有两个相邻的 边接收相同的颜色,并且最多使用k种颜色。 A组UV(G)称为团,如果它在G中导出一个完全图。一个团被称为最大的,如果它没有适当地包含在任何其他团。G中的单纯点是指只属于G的一个极大团的点。2回调和多回调功能一个函数f:V(G)→V(GJ)称为拉回,如果它是一个同态(即对所有uv∈E(G),我们有f(u)f(v)∈E(GJ)),并且如果f是内射的,当限制到NG[u]时,对所有u∈V(G)。引理2.1([2,3])若f是从G到Gj的拉回,λJ是GJ的边染色,则函数λ(uv):=λJ(f(u)f(y))是G的边染色.GC CGJ0C2a b a b a0 1 2Δ01= 3a a1CΔ = 3图1. 从指数图G到G′的回调示例:= K4定义2.2设G=(V,E)e是一个图,其中E/=1且dlet{E1, . ,Et}e是E的一个分拆. 从G到t个图的集合{G,1, . ,GJt}是t个函数{f1,.,f t},使得:(i) fi是从G[Ei]到GJi的拉回;(ii) 存在整数k中的某个位置v e和k-边着色λJ1 , … ,λJt 的 GJ1 , . , GJT,分别是λj1, . . . , G j t 的 边 着 色 。 ,λJt和回调f1,., f t在G的边缘上不产生任何颜色冲突,也就是说,函数定义为:λ(uv):=λji(fi(u)fi(v))是G的一个真k-边染色,其中Ei是uv所属的划分集.128JP W Bernardi等人/理论计算机科学电子笔记346(2019)12512Δ4----.注意在定义2.2中包括(ii)的必要性,否则回调f1,..., f t可以定义不相容的边着色(也就是说,当组装所有边着色以构造G的边着色时,可以创建颜色冲突)。同样在定义中,观察到不相交性仅在划分的集合之间被假设E1,...,t,但不是在函数的域之间,F是顶点的集合,而不是边的集合。这意味着单个顶点u可以是通过回调fi映射到GJi的顶点v,并通过一个回调fj,取决于我们希望u承担哪个角色,以便为每个边入射到u。图2示出了函数f1、f2、f3的集合的示例,其可以被验证为从Δ = 5的PCAC图G到K6的多重拉回,在K6的5-边着色λJ1=λJ2=λJ3=:λJ(uv)= (u+v)mod Δ, 如果u和v都不是Δ;(2v)mod Δ,如果u= Δ。(一)GGJ1=GJ2=GJ3=K60 3G[E1]1Δ2G[E2]G[E3]30042∗1∗4图2.在(1)中定义的5 -边着色下从G到K 6的多回调的示例。注意,标有星号的顶点被f 2和f 3映射到两个不同的顶点,没有创建颜色冲突。3结果真圆弧图具有连续1对于这样的顶点,存在循环序,即对于每个边-u→v,沿着这个顺序的边的方向,u和u之间的所有顶点都是顺时针的,v在原无向图中导出一个完全图。这种顺序称为适当的圆弧顺序。引理3.1设G是奇最大度的PCAC图。若G有泛点,或G的半核是一个独立图,则G是1 类图。JP W Bernardi等人/理论计算机科学电子笔记346(2019)125129≥--∩···⊂∪关于 我们{}{}{}证明首先观察到,如果G有一个泛顶点,则G是KΔ(G)+1的子图,因此是类1。另一方面,如果G的半核是独立图,则G也是1类,因为图的色指数相等 并且由于所有奇最大度的异差图都是1类[2]。Q下面的引理3.2提供了不满足引理3.1的真圆弧弦图的结构的完整表征。引理3.2如果G是一个最大度数为奇数且没有泛顶点的PCAC图,使得G的半核S不是一个独立图,则S=G,并且存在V(G)的一个6-划分YA,YAB,YB,YBC,YC,YAC,它将G的任意真圆弧阶σ按如下方式划分为σ的六个连续的顶点,即,作为划分中每个集合的基数,用带相应下标的σy表示:(i) 图G恰好有四个最大团,它们可以由XA:=YAB给出YAY AC,X B:=Y BC黄蓝Y AB,X C:=Y ACYCY BC和Z=Y AB Y AC Y BC,其中,在不失一般性的情况下,假设XA具有集团XA、XB和XC中的最大大小,这些集团是在σ中连续出现的集团(即,这些集团中的每一个中的所有顶点在σ中连续出现);(ii) YAB和YAC中的所有顶点都在G中有度Δ(G);(iii) Δ(G)=yA+yB+yAB+yBC+yAC−1 =yA+yC+yAB+yBC+yAC−1;(iv) yA≥yB=yC;证明令σ是G的一个真圆弧序,令(X0,X1,,X t−1)是在σ中连续出现的最大团。我们必须有t3,否则就可以直接证明G是一个自洽图.我们主张不存在X i使得X iX(i−1)modtX(i+1)modt。 如果这主张认为,通过从每个X i X(i+1)modt中选择一个顶点,可以容易地获得大小为t的诱导圈。因为G是弦的,它不是一个独立图,我们有t=3。在σ中连续出现的G的这三个最大团分别是XA、XB和XC由于G不是一个独立图,我们有两个凝聚团在σ中的交集不是空的(否则在G的任何圆弧模型中,圆周上会有一个点不被任何弧覆盖)。我们定义集合YAB:=XA<$XB,YBC:=XB<$XC,和YAC:=XA<$XC,以及YA:=XA\(YAB<$YAC),YB:=XB\(YAB<$YBC),和YC:=XC\(YAC<$YBC)。由于YAB<$YBC<$YAC中的所有顶点都是彼此相邻的,因此存在第四个最大团Z:=YAB<$YBC<$YAC,它在σ中不连续出现。到目前为止,我们已经证明了,如果这个主张成立,那么至少有三个最大的团(XA,XB和XC)在σ中连续出现,以及第四个团Z。我们还证明了集合YAB、YBC和YAC不是空的。我们可以进一步证明集合YA、YB和YC是非空的,这等价于证明每个团XA、XB和XC都有一个单纯形。130JP W Bernardi等人/理论计算机科学电子笔记346(2019)125∅/----∪∪--∩\∩\我的天联系我们XAYAYABYAC黄蓝YCXBYBCXC顶点如果Y A=,那么Y BC的每个顶点都是通用的(见图3),这与假设相矛盾。YB和YC的非空性也是类似的。图3. 根据引理3.2的PCAC图的结构。现在我们将证明这一主张,并且XA、XB和XC是σ中唯一连续的最大团。为了矛盾起见,假设在σ中存在第四个最大团XD。因为交集YAB、YBC和YAC都是非空的,所以团XD必须包含在来自XA、XB和XC的两个团的并集中。不失一般性,XD XA XB。通过上述相同的论点,四个集合(X DX A)(X B)XC),(X DX B)(X A)X C),(X BX C)X D和(X CX A)XD都是非空的。因此,通过选择四个顶点,从这些集合中的每一个中选择一个,我们得到大小为4的诱导圈,这与G是弦的事实相矛盾。因此,我们已经证明了XD不存在,并且这个主张成立。此外,由于YA、YB和YC中的所有顶点都是单纯的,所以唯一可以在σ中不连续形成的最大团是团Z(回忆图3)。在不失一般性的情况下,假设XA是XA、XB和XC中的最大尺寸,则仍然需要证明(ii)显然,G中最大度的顶点在YAB YBC YAC中。 我们将证明YAB和YAC,或者所有来自YAB,YAC,YBC的集合都有最大度的顶点(这证明了(ii))。若Y AB,Y AC,Y BC中只有一个集合I在G中有最大度的顶点,则必有YI=YBC,是XA的基数y上的乘积的原因。如果I=YAB,则G的半核是一个指数图,因为阶YB,YBC,YAB,YAC,YA是指数阶7。 I=YAC的情况类似地遵循。注:这也证明了G的半核等于G。请注意,属于来自YA,YAB,YB,YBC,YC,YAC的同一集合的顶点具有相同的闭邻域,因此具有相同的度。设u是YAB中的一个顶点,v是YAC中的一个顶点,w是YBC中的一个顶点。我们知道Δ(G)=dG(u)=dG(v)≥dG(w),并且:dG(u)=yBC+yB+yAB+yA+yAC−1;dG ( v )=yAB+yA+yAC+yC+yBC−1;dG ( w )=yAB+yB+yBC+yC+yAC−1。7一个无差图的无差序是顶点的线性序,使得属于同一个极大团的顶点按此顺序连续出现[8]。JP W Bernardi等人/理论计算机科学电子笔记346(2019)125131≥∩||联系我们从这些方程中,我们得到(iii)和y B=y C和y A y B,从而完成了(iv)的证明。Q定理3.3每一个最大度为奇数的真圆弧弦图都是第一类图。证明根据引理3.1,设G是一个最大度为奇的PCAC图,且G没有泛点,使得G的半核不是一个独立图。还令{YA,YAB,YB,YBC,YC,YAC}是V(G)的一个划分,如引理3.2中所示(回忆图3)。设{E1,E2,E3,E4}是E(G)的划分,定义为:E1:=E(G[YA<$YAB<$YB<$YBC<$YAC]);E2:={uv:u∈YACandv∈C};E3 : ={uv :u∈YBCandv∈C};E4:=E(G[C]).设V(KΔ(G)+1)={0,.,Δ(G)}和V(K yC)={0,.,c− 1}。 我们将构造一个多回调{f1,f2,f3,f4},其中fi:Vi → GiJ,对于所有i ∈ {1,.,4},是V1:=YAYABYBYBCYAC,V2:=YACYC,V3:=YBCYC,V4:=YC,并且是GJ1:=GJ2:=GJ3:=KΔ(G)+1和GJ4=KyC,在由λJ1:=λJ2:=λJ3:=λJ定义的边着色λJ1,λJ2,λJ3,λJ4下,其中λJ是在(1)中定义的KΔ ( G) +1的Δ(G)-边着色,并且λJ4是由下式定义的KyC的Δ(G)-边着色:F4J(uv)=(2yAC+yA+yC+yBC+u+v)mod Δ(G).注:λJ是KΔ(G)+1的最优边染色(它是1类,因为Δ(G)是奇数),λ4肯定不是最优的,因为cΔ(G)−2。由引理3.2说明V1=Δ(G)+1。为了定义f1,取任何满足以下条件的双射标记函数:f1(Y AC)={0,.,yAC−1};f1(Y A)={y AC,.,y AC+y A−1};f1(Y B)={y AC+ y A,., y AC+ y A+ y B− 1};f1(YBC)={yAC+ yA+ yB,..., y AC+ y A+ y B+ y BC− 1};f1(Y AB)={y AC+ y A+ y B+ y BC,..., y AC+ y A+ y B+ y BC+ y AB−1}。这里,我们用f1(Z)表示zZf1(z). 注意,我们使用了Δ(G)+ 1个不同的标签,从0到Δ(G),很容易意识到这个标签是从G[E1]到GJ1的拉回。132JP W Bernardi等人/理论计算机科学电子笔记346(2019)125它仍然要对与Y C的顶点相关的边着色,也就是说,它仍然要定义f2,..., f4。注:G[E2<$E3]是一个二部图,其部分为YC,JP W Bernardi等人/理论计算机科学电子笔记346(2019)125133∪{}∈−ACCBCYBCYAC,G[E4]是完全图.图4表示集合YBC、YC和YAC。图4. 集合YBC、YC和YAC回想一下G[E2]是由YAC和YC之间的边导出的二部图,注意与YAC中的顶点关联的边不与YB中的顶点关联。这就是为什么我们可以通过给YAC的顶点赋予它们已经被f1赋予的相同标签,并给YC的顶点赋予它们已经被f1赋予YB的顶点的相同标签来定义f2的原因,其方式将在下文中阐明。当yB=yC时,YC的所有顶点都有足够的标签。类似地,图G[E3]是由YBC和YC之间的边导出的二部图.请注意,Y BC中的顶点不是Y A中顶点的邻居,因此,如果Y BC中的顶点被f 3分配了与f 1相同的标签,则f1分配给Y A中顶点的标签可以被f3重用到Y C中的顶点(以我们在续集中阐明的方式)。记得yA≥yC,所以会有足够的标签。为了完成证明,只需要定义由f2、f3和f4赋予YC中每个顶点的三个标签,并证明通过这些拉回获得的边着色不会在G中产生颜色冲突。设YC=u0,.,u yC−1. 我们为每个u iY C定义三元组(f2(u i),f3(u i),f4(ui)):=(y AC+ y A+ i,y AC+ i,i)。 设λ是G的Δ(G)-边染色,如定义2.2所示。我们证明了λ是一个真边染色,对于λ,它表明所有的入射到YC中相同顶点ui的边的颜色是不同的。入射到ui的边的颜色可以验证为如下(下面列出的所有颜色都是modΔ(G),但为了清楚描述,省略了此信息):• 入射到ui的G[E2]的边的颜色是来自集合的yAC{yAC+ yA+1,..., 2y AC+ y A+ i − 1};• 入射到ui的G[E3]的边的颜色是来自集合的yBC{2yAC + yA+ yB+1,..., 2y AC+ y A+ y B+ y BC+ i − 1};• 入射到ui的G[E4]的边的颜色是集合中的yC1颜色{2yAC +yA+yB+yBC+1,...,2yAC+yA+2yB+yBC+i}\{2yAC+yB+yB+yBC+2i};注意,在入射到ui的边缘处,不使用(2yAC+yA+i)mod Δ(G)和(2yAC+yA+yB+i-1)mod Δ(G)之间的yB颜色,以及颜色134JP W Bernardi等人/理论计算机科学电子笔记346(2019)125∈(2yAC+yA+yB+yBC+2i)mod Δ(G).AsyAC+yB+yBC+yC≤Δ(G)=yAC+yBC+yAB+yA+yC−1,则在ui处没有颜色冲突。由于我们已经证明了在任何顶点ui YC上都没有颜色冲突,我们得出结论G是Class 1。Q引用[1] 伯纳德,J.P.W.,S. M. Almeida和L. M. Zatesko,关于适当圆弧图的总边着色,在:巴西计算机学会第3873比76网址http://natal.uern.br/eventos/csbc2018/wp-content/uploads/2018/08/Anais-ETC-2018.pdf[2] 菲格雷多角M. H、Meidanis和C. P. Mello,关于边着色独立图,Theor. Comput. Sci. 181(1997),pp. 91比106[3] 菲格雷多角M. H、Meidanis和C. P.Mello,对偶弦图的全色数和色指数,Inf.Process。Lett. 70(1999),pp. 147-152[4] Garey,M.R.,D. S. 约翰逊,G。L. Miller和C.H. Papadimitriou,着色圆弧和和弦的复杂性,SIAM J.代数离散方法1(1980),pp.216-227[5] 霍耶岛边着色的NP-完备性,SIAM J. Comput. 10(1981),pp. 718-720.[6] 约翰逊,D。美国,NP-completeness column:an ongoing guide,J. Algorithms6(1985),pp. 434-451[7] 马查多河 C. S.和C. M. H. Figueiredo, Decompositions for edge-colouring join graphs and cobipartitegraphs,Discrete Appl. Math.158(2010),pp. 1336-1342年。[8] 罗伯茨,F。美国,《独立图》,载:第二届安娜堡图论会议论文集,安娜堡,美国,1969年,页.139-146。[9] Tucker,A.,圆弧图的矩阵刻画。,Paci fic J. Math.39(1971),pp. 535-545网址https://projecteuclid.org:443/euclid.pjm/1102969574[10]Vizing,V.G.,关于p-图的色类的一个估计(俄文).分析。3(1964),pp. 25-30
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功