具有稀疏三角形的可平面图的3列表可染性

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:liuzhuoran
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如果一个图G能够嵌入到平面内,使得边仅在端点处相交,则称G是可平面图.两个圈的距离是指两个圈上的点的距离的最小值.在本文中,3圈又叫做三角形. 对于一个可平而图G=(V, E),若存在一个映射φ:V→(1,2,…k),满足,对()uv∈E,有φ(u)≠φ(v),则称φ是G的一个顶点k染色.若G存在一个顶点k染色,则称G是k可染的.使得G是k可染的最小正整数k,叫做G的染色数,用χ(G)表示.给图G的每一个顶点v分配一张色表L(v),称L={L(v)|()v∈V)是G的一张色列表.设L是G的一张色列表,若存在一个映射φ,满足(1)()V∈V,有φ(V)∈L(V);(2)()uv∈E,有φ(u)≠φ(v),则称G是L可染的.若对G的每一张满足|L(v)|≥k,()v∈V)的色列表L,G都是L可染的,则称G是k列表可染的.使得G是k列表可染的最小正整数k,叫做G的列表染色数,用ch(G)表示. 在1996年,Gutner证明了:确定一个平面图是3列表可染的是NP困难的.这样,研究平面图是3列表可染的充分条件就有意义了. 本文主要关注的是具有稀疏三角形的平面图的3列表可染性,主要证明了以下几个结论: 1.每一个不含4,6,8圈且任意两个三角形的距离至少为2的可平面图是3列表可染的. 2.每一个不含4,7,9圈且任意两个三角形的距离至少为3的可平面图是3列表可染的. 3.每一个不含4,8,9圈且任意两个三角形的距离至少为3的可平面图是3列表可染的.
其他文献
本文所研究的内容分为两部分.一、加权Bergman空间与Zygmund空问之间广义Cesaro算子和复合算子的乘积算子的有界性和紧性特征:二、Schatten-p类Hankel算子在调和Bergman空间上
本文主要建立了一个多指标交通网络平衡模型和一个多指标供应链网络模型,研究了广义(弱)向量平衡流与(弱)向量变分不等式解、(弱)h-平衡流与广义(弱)向量平衡流之间的关系,标量