Dissertation > Excellent graduate degree dissertation topics show

Edge Colouring of the Planar Graph with Some Special Conditions

Author: WangHui
Tutor: WuJianLiang
School: Shandong University
Course: Operational Research and Cybernetics
Keywords: planar graph edge coloring short cycle adjacent intersecting
CLC: O157.5
Type: Master's thesis
Year: 2010
Downloads: 28
Quote: 0
Read: Download Dissertation

Abstract


All of the graphs discussed in this paper are simple, undirected and finite. For one graph G=G(V(G),E(G)), V(G) and E(G) separately mean vertex set and edge set. For the vertex v∈V(G), d(v) is used to show the degree;△(G) andδ(G) each mean the maximum and minimum degree of the vertex in G, simply marked as△andδ. In graph theory symbols, the letters V,E,v andεare generally used to take the place of V(G), E(G), v(G) andε(G).The coloration of graphs is one of the main problems to be studied for graph theory. The graphs coloring can generally be divided into edge coloring, vertex coloring, total coloring and other specific colorings. This paper mainly discusses the edge coloring of planar graph and proves two main conclusions.A k-edge proper coloration of Graph G is a distribution of " k " kinds of colors on E(G) in such a way that the two adjacent edges are colored different colors. If there is a k-edge proper coloration of Graph G, then G is k-edge colorable. The edge chromatic number of graph G is the minimum value that makes G the k-edge colorable, marked as x (G). The following is the famous theorem for edge coloring.Vizing’s theorem(1964) supposes that G is not a empty simple graph with no loop, then there is A(G)≤x’(G)≤A(G)+1.For the graph G with multiple edges, supposingμ(G) represents the max multiple number of each edge, then as a matter of fact, Vizing’s theorem proves a more general conclusion:A(G)< x’(G)≤A(G)+μ(G).Vizing’s theorem puts forward a classification problem:if G meets the requirement x’(G)=A(G), then G is called the graph of class one; if G satisfies x’(G)= A(G)+1, then it is called the graph of class two. It is very difficult to confirm whether a graph belongs to which class, and at present only a few graphs are clearly classified. The graph of class one includes path、tree and bipartite graph, even-order complete graph as well as wheels. Odd cycle and odd-order complete graphs are class two. Generally speaking, there still are not sufficient and necessary conditions to distinguish which class a graph belongs to. It is known that there are planar graphs of class two with the maximum degree 2、3、4、5. Meantime Vizing(1965) has proved that there is no graphs of class two with maximum degree above 8. Sanders and Zhao has proved that planar graphs with maximum degree 7 is the class one graphs with edge coloring. Now it is unknown to all of us whether there are the planar graphs of class two with the maximum degree 6.In this paper, the edge-coloring problem of planar graphs is mainly studied, and short cycle means these cycles that length is equal or lesser than 5. By redistributing the value of vertex and face and applying Euler’s formula, the paper proves the following theorem:if G is a planar graph with△(G)=6, and there is no adjacent short cycles, then x’(G)=6; if G is a planar graph with A(G)=5, and there is no intersecting 3-cycle and short cycle, then x’(G)=5, that is to say, G is the graph of class one.

Related Dissertations

  1. The Analysis and Comparison of Adjacent Segment Degeneration of the Finite Element Caused by Three Posterior Lumbar Fusion Style,R687.3
  2. Research on Environmental Adjacent Right,D923.2
  3. About two parameters characteristic polynomial and its applications,O157.5
  4. Studies on the Mesozooplankton and Microzooplankton Community in the Yellow River Estuary and its Adjacent Area in Summer and Autumn,Q958.8
  5. Conversations Analysis of Medium Oral Chinese as a Foreign Language,H195
  6. The Surrounding Rock Monitoring and Finite Element Simulation of Subway Tunnel,U455.43
  7. Research on Dim Small Targets Detection in Infrared Images,TP391.41
  8. Study of Multi-site Co-scheduling Problem Based on Beijing-Hangzhou Grand Canal,U697
  9. LGR5 in hepatoma cells , liver cancer tissues and its clinical significance,R735.7
  10. Subway tunnel construction of adjacent buildings security risks,U455.1
  11. Experimental study simulated cold water seepage along River Drainage Area,TV131.6
  12. On Two Coloring of Planar Graphs,O157.5
  13. Star Coloring and Strong Edge Coloring of Graphs,O157.5
  14. A Number of Parameters Research on Coloring of Graphs,O157.5
  15. Flatbed multi-motor drive with traction control study,U464.142.1
  16. Research the 3.0T MRI Features, Diagnosis Value and Optimization of MRI Diagnostic Indicators about Breast Cancer,R737.9
  17. Expression and Clinical Pathological of VEGF、KAI-1、c-kit in Triple-negative Breast Cancer,R737.9
  18. Law and Social Norms: A Perspective of Game Theory,D90
  19. GSM the Elevated wireless network planning program,TN929.532
  20. Doppler Frequency Offset Estimation Algorithm for TD-SCDMA System in High-speed Environment,TN929.533
  21. Deformation-property Study of Deep Excavation Supported by Steel Pipe Sheet Pile in Sea Reclamation Areas,TU433

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