边着色相关论文
1974年,I.T.Jakobsen提出临界图猜想:不存在偶阶临界图。五年之后,M.K.Gol’dberg构造出无穷多个偶阶的3-临界图。1980年,M.A.Fiol......
图G的边着色是对G的边进行着色,图G的正常边着色是使得G中没有相邻的边染相同颜色的边着色。图G的正常边着色中所用颜色的最少数目......
Ramsey理论是组合数学与图论的主要研究内容之一。Ramsey数的确定是Ramsey理论中的一个重要研究方向,该问题不仅在数学的发展中有着......
Ramsey理论是图论的重要研究内容之一,而3色Ramsey数理论是其中一个重要的理论分支,对于3色Ramsey数的确定也是一个重要的研究方向......
该文讨论了图的四种不同类型的着色,即边着色、路着色、子着色、d-距面着色.利用重新着色的办法,部分地证明了Albertson和Haas提出......
由Vizing定理可知所有的k_正则简单图可分为两类:边色数为k的第工类图和边色数为k+1的第II类图。很多著名的问题限制在第工类图上......
无环图G的一个边着色π是从边集E到颜色集C的一个映射π:E→C,使得G中任何两条相邻的边均有不同的像。若|C|=k,则称π是G的一个k-边着......
学位
超图是一般图的重要推广,超图的着色概念也是一般图着色概念的自然推广。对于超图的着色有很多各种各样的应用背景,如时间表问题,资源......
对任意的一个图G,Chartrand et al.在[9]这篇文章中定义了图的彩虹连通数和强彩虹连通数。给一个图的边着色,如果图上任两个顶点间都......
用r种颜色对图G的所有边着色,记着第i色的边构成的子图为Gi,如果存在一种着色方法使得对所有的1≤i≤r都满足HiGi,则称图G对于(H......
对于无向有限简单图G和H,边Ramsey数R(C,H)是指最小的整数e,使得对一个有e条边的图的边用红蓝两色进行2-染色后要么得到一个红色的......
给出了边矩阵的定义,提出了求解完备匹配Mi的2种算法其中算法A是利用边矩阵K′2n的Δ(G)-边着色求Mi,算法B是利用边矩阵K′2n的2......
设图G为含有三角形或四边形的三次图,G_△为G的二角形收缩;G_□为G的四边形收缩。本文用计算机辅助证明了,若L(G)是2类的,则L(G_□......
在排课系统当中,调课是重要的一环。通过对调课引起的“连锁反应”特点的研究,发现如果在指定的两个时间段之间交错调整相关课程,则可......
讨论完全图Kn的任意二边着色,在Kn二边着色具有两个单色三角形的基础上,用组合的方法推得:当n≥7时,存在两个元公共边的单色三角形......
本文对程序排课问题的近似算法进行了探讨,提出了一种实用的近似算法,可使程序排课问题得到相当程度的解决.......
设G是无割边三正则图,θ={C1,C2,…,Ck}是G一个圈覆盖,定义一新图G(θ)=(V,E),这里V={C1,C2,…,Ck},(Ci,Cj)∈E当且仅当E(Ci)∩ E(......
著名图论专家Erdos和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ2;当最大度Δ为奇数时,χ′s(G)≤5/4......
给出了图的几个扩张变换:图的同型扩张,图的三角形扩张,图的四边形扩张.这些变换在研究最大次数较小的临界图的性质时起着重要的作......
G的k-(边)着色是一个映射π:E(G)→{1,2,…,k},使得G的相邻边没有相同的象.图G的色指数χ’(G)=min{k G有一个k-着色}.给出了最大次数为3......
为了让一个2n阶的完全图K2n变成一个可用于循环赛安排的循环赛图K2n^(i),给出了边矩阵和循环赛图的定义,提出利用边矩阵K2n的k-边着色......
本文给出了四点完全图K4的广义图K(4,n)和Griozsch图的广义图Gn的一种边关色法,从而解决了它们的分类问题。......
【正】 我们知道古典的Ramsey数具有非常深刻的组合意义,但这些整数的确定却相当困难。 1967年以后人们引进了各种广义Ramsey的概......
应用Hopfield网络模型,系统地研究了图的正常k-顶点着色,正常k-边着色以及正常k-全着色的具全算法,建立了相应的数学理论,了此领域内的某些工作。......
设p(n)是满足下列条件的最小正整数:对于任意大于或等于p(n)的正整数m,在n个顶点的完全图中有一个m边着色,使得其中的任一条长为4的路P4......
设Kn是具有n个顶点的完全图,fr(n)是满足下列条件的最小正整数:对于任意的正整数m≥fr(n),存在Kn的一个m边着色,使得Kn中的任一个Kr至少......
著名学者Daniel Krlá.,Jan Kratochvlí,Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bound-ed de......
著名学者Daniel Král. ,Jan Kratochvil, Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bounded degree......
本文给出了9-临界图边数的下界:m≥118/39n,其中n为点九,m为边数。...
用r种颜色对图G的所有边着色,记着第i色的边构成的子图为G1,如果存在一种着色方法使得对所有的1≤i≤r都满足Hi¢Gi,则称图G对于(H1,H1,…......
对于图G和图H ,Ramsey数r(G ,H)定义为最小正整数 p ,使得完全图Kp 用红、蓝两色作任意边着色后 ,总含红色子图G或蓝色子图H。以mG......
对程序排课问题的近似算法进行了探讨,提出了一种实用的近似算法,可使程序排课问题得到相当程度的解决.......
为了让一个2n+1阶的完全图K2n+1变成一个可用于循环赛安排的循环赛图K2n+1^(i)给出了边矩阵和循环赛图的定义。提出了利用边矩阵K′2n+1......
给出求R(G1,G2,G3)的一个算法,并利用它得到6个广义Ramsey数的值:R(P4,C4,C4)=9,R(P4,C4,C6)=9,R(P4,C6,C6)=9,R(P5,C4,C4)=11,R(P5,C4,C6)=9,R(P......
对于图G1、G2,2色广义Ramsey数R(G1,G2)是指最小正整数P,使得每一个p阶的图G,或者G包含G1,或者G的补图包含G2。用改进的模拟退火算法求解......
【正】本文所涉及的图均为简单图。图的边色数是映射φ:E(G)→K,其中K是色集,使得两个不相邻的边染不同色。|K|的最小值称为C的边......
两个不交图G与H的联G+H是指顶点集为V(G)UV(H),边集为E(G)LIE(H)U{xy|x∈V(G),y∈V(H)}的图.证明了当n=m+1时,联图Om+Cn是第二类图,否则,Om+Cn是第一类图;当......
给出并证明了外平面图的两个结构性质:(1)△≥5时,存在一个最小面,至多关联于一个△度点;(2)△=4且每个最小面均关联两个4度点时.存在闭......
在最大度为△的图G中,设γ表示能够△一边着色的边的最大部分,Albertson和Hass猜想:如果G是无桥平面图,且△=3和,则γ=1.我们对于n2=2证......
本文介绍了边对策着色,讨论了图G的边对策着色的性质.对几种特殊图类进行了讨论,分别确定链图,圈图及与国有关的图,扇图,Petersen图的边......
给出了边矩阵和循环赛图的定义,提出了基于n(n-1)/2个完全二分图矩阵的△(G′)-边着色求解完全图K4n的完备匹配Mi的算法。阐明了循......
设G是简单图,用颜色1,2,3……对G的边着色.如果每一顶点所关联的边上着的颜色构成一个连续的整数集合,那么就称这个边着色是连续的......