声明
Abstract
摘要
Contents
Chapter 1 Introduction
1.1 The background of the distance-2 coloring problems
1.2 Related definitions
1.3 Related work of distance-2 coloring problems in graph theory
1.4 Our results of distance-2 coloring problems
1.5 Organization of the thesis
Chapter 2 Lovász Local Lemma
2.1 Induction and history
2.2 Various versions of the Lovász Local Lemma
2.2.1 General LLL
2.2.2 Symmetry LLL
2.2.3 High probability case of LLL
2.2.5 Lopsided LLL
2.2.6 Quantum LLL
2.3 Proof of the general LLL
Chapter 3 Distance-2 coloring
3.1 Basic algorithms and some descriptions of LLL
3.2 Distance-2 vertex coloring
3.3 Directed distance-2 vertex coloring
3.4 Strong edge coloring
3.5 Directed strong edge coloring
Chapter 4 Conclusion
Bibliography
致谢