The Total Coloring Of Graph And Hypergraph

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.