关于图的距离关联着色的研究运筹学与控制论专业论文.docxVIP

山东科技大学硕士学位论文 摘要 摘 要 图 G 的关联着色是从关联集 I (G) 到颜色集合 C 的一个映射σ , 使得 G 中任何两个相 邻关联具有不同的象, 若σ : I (G) → C 是 G 的一个关联着色且 | C |= k , k 是一个正整数, 则称 G 是 k - 可关联着色的, 使得 σ 是 G 的一个 k - 关联着色的最小的 k 值称为 G 的关联 色数, 记为 χi (G) , 即 χi (G) = min{| C || σ : I (G) → C 是 G 的关联着色} . 图的 d - 距离关联着色是关联着色的一个推广. 图 G 的 d - 距离关联着色是从关联集 I (G) 到颜色集合 C ( d ) 的一个映射 σ , 使得 G 中任何两个 d - 距离相邻的关联具有不同的 象. 若σ : I (G) → C (d ) 是 G 的一个 k - d - 距离关联着色且 | C ( d ) |= k , k 是一个正整数, 则 称 G 是 k - 可 d - 距离关联着色的, 是 G 的一个 k - d - 距离关联着色. 使得 σ 是 G 的一个 ik - 可 d - 距离关联着色的最小的 k 值, 称为 G 的 d - 距离关联色数, 记为 χ (d ) (G) , 即 i iχ ( d ) (G) = min{| C ( d ) || σ : I (G) → C ( d ) 是 G 的一个 d - 距离关联着色} . i 本文研究了若干图的 d - 距离关联着色, 具体安排如下: 在第一章中, 给出了 d - 距离关联着色和 d - 距离关联色数的概念和基本性质. 在第二章中, 通过运用反证、穷染等方法, 研究了路, 圈, 星, 扇, 轮, 完全图, 完全 二部图的 1-距离关联色数. 随后, 给出了皇冠图, 广义皇冠图, 图 Ln,k , 图 Ln 的概念, 以 及它们的 1-距离关联色数. 在第三章中, 证明了路, 圈, 树, 星, 扇, 轮, 完全图, 完全二部图,  Ln,k 的 3-距离关 联色数. 论文的第四章主要研究了 d 3 时路, 圈, 星, 扇, 轮的 d -距离关联色数. 关键词: 关联着色, 关联色数, d - 距离关联着色, d - 距离关联色数 山东科技大学硕士学位论文A 山东科技大学硕士学位论文 ABSTRACT ABSTRACT Incidence coloring of G is a mapping σ from  I (G) to a color set C , such that any two adjacent incidences in I (G) are signed different images. If σ : I (G) → C is an incidence coloring of G , and | C |= k , k is a positive integer, then G is k - incidence colorable and is a k - incidence coloring of G ; 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{| C || σ : I (G) → C is an incidence coloring of G } . The d - distance incidence coloring of a graph G is a variation of the incidence coloring. The d - distance incidence coloring of graph G is a mapping from the set of incidences  I (G) to a color set C ( d ) , such that any two d - distance adjacent incidences possess distinct images. If σ : I (G) → C (d ) is a k - d - distance incidence colo