论文部分内容阅读
本文仅考虑无向有限简单图，对于一个给定的图G，我们分别用V(G)，E(G)，δ(G)，△(G)和mad(G)来表示图G的顶点集合，边集合，最小度，最大度以及最大平均度. 图G的k-injective染色是指一个映射f:V(G)→C={1，2，3，…，k}，使得对于图G中的任意两点v1，v2，若它们在G中有公共邻点，则f(v1)≠f(v2).称xi(G)=min{k|G存在一个k-injective染色}为图G的injective染色数. 图G的k-injective边染色是指一个映射f:E(G)→C={1，2，3，...，k}，若e1，e2和e3是G中的连续边，则f(e1)≠f(e3).称xi(G)=min{k|G存在一个k-injective边染色}为图的injective边染色数. 本论文分为五章，主要研究在最大度和围长，最大平均度限制下的图的injective-边染色以及Halin图的injective-染色.第一章主要介绍了本论文所涉及的相关概念，并对injective-染色(injective-边染色)的研究现状和存在的问题做了一个综述.第二章主要讨论在最大平均度限制下的一些稀疏图G的injective-边染色数的上界，第三章主要讨论了围长至少为6的平面图G是3△(G)-2可染的，第四章讨论平面稀疏图的injective-边染色数的上界，第五章讨论了Halin图的injective-染色数的上界.