【作者】 杨鹏辉；

【导师】 龚劬；

【作者基本信息】 重庆大学 ， 计算数学， 2007， 硕士

【摘要】 为了恰当地表示大型超网络、数据库系统、时间安排和线路设计等研究课题中各元素之间的关系,超图全着色理论做为一般图全着色的推广被自然的引入。由于其良好的应用背景,超图全着色理论成为现在图论领域中迅速发展的子学科之一,也是各学者们所热衷的研究方向。本文首先综述了一般图中全着色的概念和研究现状,然后自然地引入了超图中全着色的分类和概念。随后着重讨论了特殊超图,如:超星、超树等的全着色性质。在研究超星全着色时,阐述了超星不同的定义,对其进行了分类,并根据本文研究的需要,采用定义3.2为超星的概念。接着给出超星的弱全色数和强全色数表达式,并有详细的理论性证明。再根据超星的结构特征,证明了超星全着色的计数公式。最后提出了关于超星全着色的两个有效算法,同时通过两个例子说明了全色数表达式、全着色计数和算法的正确性。根据定义3.2确定的超星是线性超树的一个特例,第四章就进一步对线性超树进行研究,加深了第三章超星全着色的研究。在讨论超树全着色时,引入了一个新的概念――超树对应二部树。超树和其对应二部树是一一对应的,二部树能够完全反映超树的点边邻接关系。则根据超树和其二部树的对应关系,我们将超树全色数的求解转变成计算满足一定条件的二部树的点色数。这大大降低了计算的复杂度。无论是超星还是线性超树都是简单、有限的无圈超图,但超图中并不是只有无圈的,而且圈在全着色理论中占据很重要的位置。所以,第五章讨论了两种有圈超图的全着色。首先从一般图中轮图和扇形图的全着色入手,逐步引出超图中轮图和扇形图的概念及全色数表达式。以上几章的讨论都是围绕着特殊超图展开的,但特殊超图只占超图领域中很小的一部分,大多数的都是一般的,无特点的。第六章则给出了关于n个点m条边的线性超图全色数的两个猜想。在系统建立全着色理论的基础上,本文着重研究了几类特殊超图的全着色性质。并结合实际问题的需要,给出了一般线性超图全色数的两个猜想。最后提出关于全着色的继续研究方向:非线性超图的全色数、重图、伪图,还有现在比较热的混合超图等。更多还原

【Abstract】 In many projects like large super-network research, database systems research, timing research, circuit design research and so on, the theory of total coloring can represent relationships between elements there. Due to its good application background, total coloring theory has become a rapidly developing subject in the field of graph theory and also become one of the hot studies.Firstly, we summarize the current research on the total coloring of graph and related basic concepts, and introduce the categories and concepts of total coloring of hypergraphs naturally. Then discussing the total coloring of special hypergraphs, for example: hyperstar, hypertree and so on.We expatiate on the different concepts of hyperstar and classify it when studying the total coloring of hyperstar. Then based on the need of research, we adopt the define 3.2 as the concept of hyperstar. Next the expression of weak total chromatic number and strong total chromatic number is presented, with the detailed and reasoned proof. Then based on the structural character of hyperstar, the enumeration formulary of total coloring is proofed. At last two effective algorithms on total coloring are presented. The validity of the expression of weak total chromatic number and strong total chromatic number, the enumeration formulary and the algorithms is proofed by two examples.The hyperstar is a special roal of linear hypertrees. We will study the total coloring of linear hypertrees in chapter four. We adopt a new concept—the bitree corresponded to a linear hypertree. It can reflect the relation of vertices and edges completely, so the problem of the total chromatic number of linear hypertree is becoming solving the chromatic number of bitree corresponded to the linear hypertree. It reduces the difficulty of the question.Both the hyperstar and linear hypertree are simple, finite and acyclic hypergraph, but the hypergraph is not all acyclic ones, moreover, the total coloring of cycle is more important in total coloring theory. So we research the total coloring of two cycle-hypergraph. First, researching the wheel and fan in graph theory, then studying the total coloring of wheel and fan in hypergraph theory. At last, the expression of total chromatic number is presented. We talk about special hypergraphs from chapter three to five, but a lot of hypergraps are generally. Therefore, two conjectures on the linear hypergraph of n vertices and m edges are presented. Based on establishing systemically total coloring theory, we emphasize on the property of total coloring of some special hypergraphs. Combined with the needs of practical problem, two conjectures are presented. Finally, we provide the new research direction: the total coloring of non-linear hypergraph, multigraph, pseudograph and mixed hypergraphs.更多还原