关于图的几类着色问题的研究应用数学专业论文.docxVIP

山东科技大学硕士学位论文摘要 山东科技大学硕士学位论文 摘要 摘 要 图 G 的关联着色 ? 为由 I (G) 到颜色集 C 的一个映射 ? , 使得 I (G) 中任何相邻的关 联对都着不同的颜色 . 若 ? : I (G ) ? C 是 G 的关联着色且满足 | C |? k , k 是一个正整数 , 则称 ? 是 G 的一个 k ? 关联着色, 使得 G 存在 k ? 关联着色的最小值 k 称为 G 的关联色数, 记作 ?i (G ) , 即 ?i (G) ? min{| C || ? : I(G) ? C 是 G 的关联着色}. 邻点可区别关联着色的定义是在关联着色的基础上推广出来的 , 进一步细化了图的 着色参数: 若对任意 uv ? E(G) 满足 C(u) ? C(v) , 则称 ? 为 G 的 k ? 邻点可区别关联着色, 并称 ?ai (G ) ? min{| k | k 是 G 的 k ? 邻点可区别关联着色} 为 G 的邻点可区别关联色数. 本文从图的结构和性质出发, 利用反证法和枚举法研究一些图的邻点可区别关联着 色, 定义了图的 k ? d ? 距离可区别关联着色和点可区别关联着色 , 并确定了几类图的 k ? d ? 距离可区别关联色数和一些图的点可区别关联色数. 本文共分六章, 具体安排如下: 第二章中, 主要给出了图论的基础知识和相关引理, 并定义了三类新图. 第三章中, 主要研究讨论了 ? ? 图、广义? ?图和广义星图的邻点可区别关联着色. 第四章中, 在图的邻点可区别关联着色的基础上定义了图的 k ? d ? 距离可区别关联 着色的概念, 研究了图的 k ? d ? 距离可区别关联着色的几条性质和几类图的 k ? d ? 距离 可区别关联着色, 确定了星 Sn 、扇 Fn ?1 (n ? 3) 、轮 Wn?1 (n ? 4) 、圈 Cn (n ? 4) 和向日葵图的 k ? 2 ? 距离可区别关联色数, 以及路 Pn (n ? 5) 的几类 k ? d ? 距离可区别关联色数. 在第五章中, 在图的邻点可区别关联着色和在第四章的基础上 , 定义了图的点可区 别关联着色的概念, 并讨论了几中常见图类的点可区别关联着色 , 确定了星图 Sn 、完全 图 Kn 、扇 Fn ?1 (n ? 3) Fn ?1 (n ? 3) 、轮 Wn?1(n ? 4) 和 C5 的点可区别关联色数, 并确定了路 Pn (n ? 3) 和圈 Cn (n ? 4) 的点可区别关联色数下界. 关键词: 邻点可区别关联着色, k ? d ? 距离可区别关联着色, 点可区别关联着色 山东科技大学硕士学位论文AB 山东科技大学硕士学位论文 ABSTRACT ABSTRACT An incidence color ing of G is a mapping ? from I (G) to a color set C , such that any two adjacent incidences in I (G) have different ima ges. If ? : I (G ) ? C is an incidence color ing of G and | C |? k , k is an positive integer, then we say that ? is a k ? incidence color ing of  G , and the minimum value of k  such that G is  k ? incidence colorable is called the incidence chromatic number of G , and is denoted by ?i (G ) , namely ?i (G ) ? min{k | there exists an k ? incidence color ing of G}. The definition of adjacent vertex dist inguishing incidence color ing is based on the incidence color ing, which further defines parameters of graph color ing. If for any uv? E(G) , C(u) ? C(v) , then we call ? a k ? adjacent vertex dist inguishing incidence color ing of G . And