Dissertation > Excellent graduate degree dissertation topics show

On Two Coloring of Planar Graphs

Author: WuYanQing
Tutor: XieDeZheng
School: Chongqing University
Course: Applied Mathematics
Keywords: lanar graph acyclic edge coloring acyclic edge chromatic number total coloring total chromatic number
CLC: O157.5
Type: Master's thesis
Year: 2011
Downloads: 25
Quote: 0
Read: Download Dissertation

Abstract


All graphs considered in this thesis finite and simple. For any graph G, we denote its vertex set, edge set and face set by V(G), E(G) and F(G).The colouring c is proper if no two adjacent edges have the same colour for graph G. A proper edge colouring c is called an acyclic edge coloring if there are no bichromatic cycles in the graph G. The acyclic edge chromatic nunmber is the least number of colors in an acyclic edge coloring of G. The acyclic edge k-coloring of a graph G is that there exists an acyclic edge coloring using k colors. In 2001, Alon et al gave the following conjecture(AECC for short).Conjecture 1. For any graphs G, then the acyclic edge chromatic nunmber is less than or equal maximum degree plus 2.A total coloring of a graph G is a mapping c which is form the union of the vertex set and edge set to color set C such that coloring different for every pair of adjacent or incident elements. The total chromatic number of G is the least number of colors in a total coloring of G. Behzad and Vizing gave the following conjecture (TCC for short).Conjecture 2. For any graphs G, then the total chromatic nunmber is greater than or equal maximum degree plus 1 and less than or equal maximum degree plus 2 .The thesis investigate two coloring of a class of planar graphs G, the acyclic edge coloring and the total coloring. The concrete contents and results are as follows:Firstly, the thesis summarize the current reseach on two coloring of graphs and related basic concepts, the acyclic edge coloring and total coloring.Secondly, the thesis give an upper bound on the acyclic edge chromatic number for planar graphs without 5-cycles, planar graphs with girth at least four, planar graphs without adjacents, planar graphs without 4-cycles, planar graphs not containing cycles of length 4 and 5 and planar graphs not containing any cycle of length 4,6 and 8, respectively.Finally, the thesis give planar graphs with maximum degree six contain neither 3-face with 5-vertex nor (4,6,6)-face, TCC holds.

Related Dissertations

  1. Group Chromatic Number of Some Kinds of Graphs,O157.5
  2. On the Dmarandachely Adjacent Vertex Distinguishing Total Coloring of Several Kinds Graph,O157.5
  3. Total Coloring of Plane Graph with Maximum Degree at 6,O157.5
  4. Acyclic Edge Coloring of Plane Graphs,O157.5
  5. Some Results of Vertex-distinguishing Edge Coloring of Graphs,O157.5
  6. Adjacent Vertex Distinguishing Total Coloring of Several Graphs,O157.5
  7. On the adjacent vertex distinguishing total coloring of some of the results,O157.5
  8. The Vertex-Adjacent Vertex Distinguishing Total Coloring of Some Graphs,O157.5
  9. The New Coloring Problems of Some Graphs,O157.5
  10. The (p,1)-Total Labeling of Graphs and the Problem of Weak Adjacent-Vertex-Distinguishing Colouring of Graphs,O157.5
  11. Total Coloring of Plane Graphs with Maximum Degree at Least 7,O157.5
  12. On the adjacent vertex distinguishing total coloring of,O157.5
  13. Staining adjacent vertex distinguishing total coloring and two special issues,O157.5
  14. The Research of Algorithm for Strong Vertex-distinguishing Total Coloring,O157.5
  15. Adjacent vertex distinguishing total coloring and edge coloring,O157.5
  16. The point on the map coloring problem distinguishing,O157.5
  17. Total Coloring of Plane Graphs,O157.5
  18. Total Coloring of Planar Graphs without Adjacent Short Cycles,O157.5
  19. The Total-Coloring Critical Graph and Adjacent-Vertex-Distinguishing Total Coloring,O157.5
  20. Equitable Total Coloring of C_m□C_n and P_m□C_n,O157.5
  21. The Total Chromatic Number of Some Particular Planar Graphs,O157.5

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory
© 2012 www.DissertationTopic.Net  Mobile