Study On The Group Coloring Of The Plan View And The Non-claw Graph

The coloring theory is one of the hot topics in graph theory.The equitable coloring theory is the further development of coloring theory.It is now widely used in chemistry,biology,computer science,industrial production and enterprise management.The research of clique-coloring is a variant of vertex coloring.The clique-coloring is also called weak coloring.In this paper,we mainly study the clique-coloring problem and the equitable clique-coloring problem.It has impor-tant application background and theoretical value to study the clique-coloring and the equitable clique-coloring of graphs.In Chapter ?,we first introduced the basic concepts and definitions required for this article.Secondly,the research significance of this topic is introduced.Finally,we summarized the research progress of clique-coloring in recent ten years.In Chapter ?,we mainly research the clique-coloring of planar graphs.Mo-har and?krekovski proved that planar graphs are 3-clique-colorable(Electr.J.Combin.6(1999),#R26).In this chapter,we use inductive method to further prove that arbitrary planar graphs are 3-clique-coloring.In addition,we derive a linear time algorithm for the 3-clique-coloring of planar graphs.(The results were published on0)(64)9)0)0)(6(8?0)0)).In Chapter ?,we mainly research the equitable clique-coloring of claw-free graphs.Bacs?o and Tuza proved that connected claw-free graphs with maximum degree at most four,other than chord-less odd cycles of order greater than three,are 2-clique-colorable and a 2-clique-coloring can be found in(9)~2)(Discrete Math.and Theor.Comput.Sci.,2009,11(2),pp.15-24).In this chapter,we use inductive method to prove that every connected claw-free graph with maximum degree at most four is equitable 2-clique-coloring except for the chord-less odd cycle of order greater than three.Thus further improving the results of Bacs?o and Tuza.In addition,we have improved the algorithm shown in this mentioned literature that the graph of this class is equitable 2-clique-coloring in linear time.