乘积图的多彩着色

摘要

图的顶点着色是图论中的重要研究专题，在实际生活中有着极其广泛的应用.诸如学生选课，四色问题，会议安排，中继站分配特别是计算机网络方面许多问题都能转化为顶点着色问题.图的r-多彩着色是正常项点着色，且满足每个度数为d(v)的顶点其邻点的颜色数至少为min{d(v)，r}.它把图的正常着色（1-多彩着色），动态着色(2-多彩着色)，平方着色（Δ-多彩着色）都包括在内，是一种非常有意义的新着色.确定一个图能否进行r-多彩着色的最小颜色数也就是r-多彩色数，是该专题研究的首要任务.
　　圈和路是最基本的图类,文献[1]中给出了它们最基本的结论.图G的l次方Gl是图的基本概念，其顶点与图G相同，两个顶点相邻当且仅当是图G中两个顶点的距离不超过l.本文首先讨论了路和圈的l次方多彩色数，并且研究了平方圈和平方路的r-多彩色数.
　　笛卡尔积和强积作为图运算的基本形式，在[8][10],[12，13]中作者研究了有关乘积图的多彩色数和r-多彩色数.在此基础上，本文研究平方圈，平方路与路的笛卡尔积，路与路，路与圈强积图的多彩色数和r-多彩色数并得到一些比较好的结论.
　　本文中主要通过证明图的多彩着色数，r-多彩色数的上下界相等而获得确切值，其中上界是通过运用相关代数运算给出具体着色方式而获得的，下界是通过反证法及严密推理得到的.

目录

声明

摘要

Abstract

Chapter 1 Introduction

1．2 Studying Background

Chapter 2 2-Hued Colorings of Pln and Cln

Chapter 3 r-Hued Coloring of P2n，C2n，and their Cartesian Products with Pm

Chapter 4 r-Hued Colorings of Strong Products of Pn and Pm，Pn and Cm

结论

参考文献

致谢

攻读学位期间发表的学术论文