Dissertation > Excellent graduate degree dissertation topics show

On Chromatic-Choosable of One Class of Complete Multipartite Graphs

Author: TangQing
Tutor: ShenYuFa
School: Hebei University of Technology
Course: Applied Mathematics
Keywords: list coloring chromatic-choosability ohba’s conjecture com-plete multipatite graph
CLC: O157.5
Type: Master's thesis
Year: 2011
Downloads: 11
Quote: 0
Read: Download Dissertation

Abstract


List coloring of graph has become one of the hottest researching points formany scientists in the world. In this paper, we study the chromatic-choosability ofgraphs on list coloring. A graph G is called chromatic-choosable if Ch(G) =χ(G).For the choosability of graphs, Ohba conjectured that every graph G with 2χ(G)+1or fewer vertices is chromatic-choosable in 2002. It is easy to see that Ohba’sconjecture holds if and only if it holds for complete multipartite graphs. The graphfor which Ohba’s conjecture has been verified are some complete multipartitegraphs. In this paper, we show that graphs Ks+3,3*t,2*(k-s-2t-1),1*(t+s)￡t≥0; k≥s + 2t + 1; 2≤s≤5)are chromatic-choosable. Hence Ohba’s conjecture holdsfor Ks+3,3*t,2*(k-s-2t-1),1-(t+s)￡t≥0; k≥s + 2t + 1; 2≤s≤5)and all k-chromaticsubgraphs of them.This paper includes five chapters: The first chapter is introduction, introducingthe phylogeny of graph theory, and the researching purpose and meanings of thispaper; The second chapter is preparative knowledge in which we give some infor-mation on graph and some concept of graph; In the third chapter, we introduce thecurrent situation and obtained consequence on chromatic-choosable research; Inthe forth chapter, we prove the chromatic number of one class of complete multi-partite, and verify Ohba’s conjecture; In the last chapter, we sum up what we havedone in this paper.

Related Dissertations

  1. Equitable Colorings of Graphs,O157.5
  2. List Edge Coloring and Linear Coloring of Planar Graphs,O157.5
  3. The List Point Arboricity of Graphs,O157.5
  4. Discussion of the relationship of the unique vertex coloring , only a list of coloring the overall structure of their coloring parameters,O157.5
  5. The Complete Tripartite Graphs K2,2,r（r=4,5,6） Have Property M（3）,O157.5
  6. A Characterization of Uniquely List Colorable for Some Complete Multipartite Graphs,O157.5
  7. On Uniquely List Colorable Complete Multipartite Graphs,O157.5
  8. On the Total Coloring、Entire Coloring and Choosability Coloring of Some Graphs,O157.5
  9. 4-Choosability of Toroidal Graphs Without 4-Cycles,O157.5
  10. The List Coloring of the Bipartite Graphs,O157.5
  11. Equitable Colorings of Graphs,O157.5
  12. Some Topics on Restricted Coloring Problems of Graphs,O157.5
  13. The Research on Some Parameters in Graph Coloring,O157.5
  14. Research on the Restricted Colorings of Graphs and Relative Problems,O157.5
  15. Research on Choosability of Graphs and Uniquely List Colorable Graphs,O157.5
  16. List Colorings and Cycle Double Cover of Graphs,O157.5
  17. On Ohba’s Conjecture of One Class of Complete Multipartite Graphs,O157.5
  18. Analysis of Complex Networks Modeling and Its Application,O157.5
  19. Network based on the provision of public goods countermeasures study strategic interaction and equilibrium problems,O157.5
  20. Application of Inclusion Principle Based on Graph Theory in Interconnected Large-scale Systems,O157.5
  21. Chromatic Equivalent Graphs of Two Kinds of Graphs,O157.5
  22. Consensus in Complex Dynamic Network of Multi-Agent Based on LMI Method,O157.5

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