排序方式: 共有5条查询结果,搜索用时 15 毫秒
1
1.
2.
图G的一个圆环r-染色(r≥2)是将G的每个顶点v对应到一个周长为r的圆上的点的一个映射f,使得对于G中任意的边xy,f(x)和f(y)在圆上的距离不小于1.G的圆环色数χc(G)是G存在圆环r-染色的最小实数r.符号图的圆环染色和图的圆环染色基本相同,不同的是对于负边xy,我们要求f(x)和f(y)的对点在圆上的距离不小于1.符号图(G,σ)的圆环色数是使得(G,σ)在圆环r-染色的最小实数r.本文证明:对于任意正整数k和实数ε> 0,存在整数g使得对于任意树宽至多为k的符号图(G,σ),如果(G,-σ)的负围长至少是g,那么(G,σ)的圆环染色数至多是2+ε. 相似文献
3.
图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题. 相似文献
4.
引入图的弱准带宽和前沿带宽,并将其应用于研究图的带宽、拓扑带宽、填充、侧廓、路宽和树宽等. 相似文献
5.
树与偏k—的乘积的树宽 总被引:3,自引:0,他引:3
本文确宇了一棵树与一个k-连通偏k-树的乘积图的树宽。其中,偏k-树是一个树宽为k的图。 相似文献
1