New Two Variables Chromatic Polynomial Theory And Applications

Graph theory is a branch of discrete mathematics, and its research field is the property, logical structure and application of graph.4CC is known as one of the World’s Three Puzzles. also it is a famous problem of graph theory. Single variable chromatic polynomial was proposed by America mathematician Birkhoff, he wanted to solve the Problem of400with it. Later. Whitney had done many effective works for it. German scholar Klaus Dohmen et al proposed a new two-variable chromatic polynomial. We found that it not only include single-variable chromatic polynomial, but also there still many important properties that haven’t been known to people. But Dohmens never continue this research at all. and we find few articles about this topic still now. Not long ago, some scholars, such as Aivaliotis and Baily. they succeed in the reliability study of rooted graph (network), combining chromatic polynomial with probability theory. Soon, the method of chromatic polynomial combined with probability became one of the most forefront methods now. In view of this, we tend to further study this new two-variable chromatic polynomial, and we hope to study rooted graph(network) with the new method of chromatic polynomial combined with probability, so that we may make more innovative results in future. So we chose this topic as my doctoral dissertation. Wre have had some rcsults(seen appended "research paper during Ph.D").The author want to give a full explanation about the theory of new two-variable chromatic polynomial and the application in rooted graphs combined it with probability. The contents of this thesis as following:we firstly introduce the theory of single-variable chromatic polynomial and graph theory, so is the related application of them. Then we introduce the notion of new two-variable chromatic polynomial, focused on the new results. Later, we introduce a new ap-plication of single-variable chromatic polynomial combined with probability, the research results of expect of rooted graph when the edge will survive with probability p after disaster happened. Later, we introduce the research of expect of rooted graph when the vertex will survive with probability p. and the optimization of whole rooted graph combined with variance. Then we introduce the research theory of new two-variable chromatic polynomial combining probability application in rooted graph, also some other discussion. We made a compare study for4famous two-variable chromatic polynomial, and we gave a part proof for Read Conjecture(UC).My contribution for the new two-variable chromatic polynomial as follows: Firstly, we found the deletion edge formula independently. We all know that the formula is very efficient and useful.Secondly, we use lattice partition method to vertices set, viewing it as partial order, then we get its two basic mobius inversion functions. Then, every graph’s chromatic polynomial can be express with this two functions. So,we re-express the significance of the new two-variable chromatic polynomial perfectly.Thirdly, we found its new application to regular q-tree and integral subgraph of regular q-tree. Fourthly, we study the expect when vertex survive with certain probability in rooted graph, most importantly, we get the deletion-contraction edge formula. Later, considering the robust-ness (variance), and combined with the expect, we discuss the optimization problem of root graph. Finally, we considered that the edges and vertices both will fail with a certain proba-bility respectively, then the reliability and robustness of the rooted graph.Fifthly, for the worldwide hard problem,-Read Conjecture(UC), we have given a part proof, that is, when its minimum degree not more than2, the conjecture is true.Sixthly, we also compare four famous two-variable chromatic polynomial as Potts, Tutte, Match-ing and Dohmen’s, and we get many useful properties, such as their reduce-edge formula and the proofs.There are five chapters in this thesis. The first chapter is introduction, we introduce notions of graph theory and single-variable chromatic polynomial briefly, including the main research objects. and their development status, unresolved important issues, and so on. The second chapter is the theory of new two-variable chromatic polynomial, including the notion, some research results of myself. The third chapter is introduction of probability and theory of single variable chromatic polynomial and its application, including Aivaliotis and Bailey’s expect value research results for rooted graph, my research for vertex survive probability and optimization of whole rooted graph. The fourth chapter is the research of reliability of rooted graph when both vertex and edge will fail with certain probability, and the entire optimization combining variance, and other possible discussions. The fifth chapter is conclusion of whole thesis, and some directions of future research.