不含相邻短圈的平面图的全染色

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

本文考虑的图均为有限、简单、无向图。对于任意一个图G，它的顶点集、边集、面集、最小度和最大度分别用V（G）、E（G）、F（G）、δ（G）和△（G）来表示．图G的一个正常全k—染色是从V（G）∪E（G）到颜色集{1，2，3…k}的一个映射λ，它使得任意相邻接或关联的元素x，y∈V（G）∪E（G），都有λ（x）≠λ（y）．如果图G有一个正常全k—染色，则称图G足全k—可染色的，定义XT（G）=min{k|G是全k—可染色的}为图G的全色数。显然，对任意图G，都有XT（G）≥△（G）+1．Behzad和Vizing在1965年分别独立提出了下面猜想：全染色猜想（TCC）：任意图G，都满足χT（G）≤△（G）+2．对于一般的图，人们已经证明当△（G）≤5时，TCC猜想成立．对于平面图，已经证明当△（G）≥7时，TCC猜想成立．从而全染色猜想对平面图只剩△（G）=6的情形尚未证明。对任意图G，如果XT（G）=△（G）+1，则称G是第Ⅰ类图；如果XT（G）=△（G）+2，则称G是第Ⅱ类图．目前，已经证明如果图G是△（G）≥9的平面图，则G是第Ⅰ类图．本文中我们主要研究不含相邻短圈的平面图的全染色问题，其中的短圈是指长度小于等于5的圈．我们通过对顶点和面上的值进行重新分配，运用欧拉公式证明了若G是△（G）=6的平面图，且G中不含相邻的短圈，则XT（G）≥8；若G是△（G）=8的平面图，且G中不含相邻的短圈，则G是第Ⅰ类图．

著录项

作者
方瑞瑞;
展开▼
作者单位

山东大学;

展开▼
授予单位山东大学;
学科运筹学与控制论
授予学位硕士
导师姓名吴建良;
年度 2009
页码
总页数
原文格式 PDF
正文语种中文
中图分类图论;欧拉积分;
关键词
平面图; 全染色; 全色数; 短圈; 欧拉公式;

相似文献

中文文献
外文文献
专利

1. 平面图不含短圈及相邻三角形的非正常染色 [J] . 聂静方 ,王应前 . 丽水学院学报 . 2016,第002期
2. 最大度为6不含相邻弦6-圈的平面图的全染色 [J] . 郭占海 ,金珩 ,常建 . 内蒙古师范大学学报（自然科学汉文版） . 2018,第005期
3. 最大度为6且不含5-圈和相邻4一圈的平面图是7-全可染的 [J] . 张静雯 . 浙江师范大学学报（自然科学版） . 2011,第003期
4. 不含短圈平面图的无圈边染色的一个结果 [J] . 张埂 . 贵州师范学院学报 . 2012,第006期
5. 不含特殊短圈平面图的无圈边染色 [J] . 郑丽娜 . 浙江师范大学学报（自然科学版） . 2012,第001期
6. 最大度是8的平面图的全染色 [C] . Wang Huijuan ,王慧娟 ,Wu Jianliang . 第十届全国博士生学术年会 . 2012
7. 不含相邻短圈的平面图的无圈边染色的一些结果 [A] . 韩徐曦 . 2016

不含相邻短圈的平面图的全染色

目录

摘要

著录项

相似文献

相关主题

期刊订阅