Spelling suggestions: "subject:"graph coloring,"" "subject:"raph coloring,""
1 |
Various coloring problems on plane graphsLi, Ching-man, 李靜文 January 2007 (has links)
published_or_final_version / abstract / Mathematics / Master / Master of Philosophy
|
2 |
On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph31 March 2009 (has links)
M.Sc. / In this dissertation we study two types of colourings, namely line-distinguishing colourings and harmonious colourings. A line-distinguishing colouring of a graph G is a k-colouring of the vertices of G such that no two edges have the same colour. The line-distinguishing chromatic number G is defined as the smallest k such that G has a line-distinguishing k-colouring. A harmonious colouring of a graph G is a proper k-colouring of the vertices of G such that no two edges have the same colour, i.e. no two adjacent vertices can have the same colour. The harmonious chromatic number hG is defined as the smallest k such that G has a line-distinguishing k-colouring. In Chapter 0 we discuss some of the terminology and definitions used later on in our study. In Chapter 1 we introduce line-distinguishing colourings and consider the line-distinguishing chromatic number of certain familiar classes of graphs such as trees, paths, cycles and complete graphs. We also consider graphs with line-distinguishing chromatic number G equal to the usual chromatic number G, and we compare G with the chromatic index G of a graph. In Chapter 2 we mostly discuss minimal line-distinguishing (MLD) colourings. We consider minimal line-distinguishing colourings and graphs of diameter two as well as classes of regular MLD-colourable graphs. We also introduce the concept of distance regular graphs and discuss minimal line-distinguishing colourings in these graphs. In Chapter 3 we introduce a new parameter, namely the upper line-distinguishing chromatic number H G of a graph. We investigate H G for paths and cycles, and consider graphs with small upper line-distinguishing chromatic numbers. In Chapter 4 we consider the second type of colouring studied in this dissertation, namely harmonious colourings. We define the harmonious chromatic number hG and determine hG for certain classes of graphs such as paths, trees, cycles and complete graphs. In Chapter 5 we discuss upper and lower bound for hG. In Chapter 6 we discuss the upper harmonious chromatic number HG of a graph, and we determine HG for paths and cycles. We also consider graphs satisfying HG G 1. The purpose of this study is to compile a resource which will give a thorough and well-integrated background on line-distinguishing and harmonious colourings. It is also intended to lay the groundwork for further doctoral studies in the field of colourings.
|
3 |
Sum list coloring and choosability /Heinold, Brian, January 2006 (has links)
Thesis (Ph. D.)--Lehigh University, 2006. / Includes vita. Includes bibliographical references (leaf 86).
|
4 |
Various coloring problems on plane graphsLi, Ching-man, January 2007 (has links)
Thesis (M. Phil.)--University of Hong Kong, 2007. / Title proper from title frame. Also available in printed format.
|
5 |
Chromatic schedulingRaman, Rajiv. January 2007 (has links)
Thesis (Ph. D.)--University of Iowa, 2007. / Supervisor: Sriram Pemmaraju. Includes bibliographical references (leaves 142-147).
|
6 |
On the Structure of Counterexamples to the Coloring Conjecture of HajósZickfeld, Florian 20 May 2004 (has links)
Hajós conjectured that, for any positive integer
k, every graph containing no K_(k+1)-subdivision is k-colorable. This is true when k is at most three, and false when k exceeds six. Hajós' conjecture remains open for k=4,5.
We will first present some known results on Hajós' conjecture. Then we derive a result on the structure of 2-connected graphs
with no cycle through three specified vertices. This result will then be used for the proof of the main result of this thesis. We show that any possible counterexample to Hajós' conjecture for
k=4 with minimum number of vertices must be 4-connected. This is
a step in an attempt to reduce Hajós' conjecture for k=4 to the conjecture of Seymour that any 5-connected non-planar graph contains a K_5-subdivision.
|
7 |
Almost regular graphs and edge-face colorings of plane graphsMacon, Lisa Fischer. January 2009 (has links)
Thesis (Ph.D.)--University of Central Florida, 2009. / Adviser: Yue Zhao. Includes bibliographical references (p. 102-104).
|
8 |
Approximate edge 3-coloring of cubic graphsGajewar, Amita Surendra. January 2008 (has links)
Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009. / Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.
|
9 |
Fractionally total colouring most graphsMeagher, Conor John. January 1900 (has links)
Thesis (M.Sc.). / Title from title page of PDF (viewed 2008/01/30). Written for the School of Computer Science. Includes bibliographical references.
|
10 |
The topology of graph homomorphisms /Dochtermann, Anton, January 2007 (has links)
Thesis (Ph. D.)--University of Washington, 2007. / Vita. Includes bibliographical references (p. 107-111).
|
Page generated in 0.1051 seconds