You are here
ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS
 Date Issued:
 2009
 Abstract/Description:
 Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A lineartime algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomialtime algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edgeface chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A wellknown result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.
Title:  ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS. 
18 views
12 downloads 

Name(s): 
Macon, Lisa, Author Zhao, Yue, Committee Chair University of Central Florida, Degree Grantor 

Type of Resource:  text  
Date Issued:  2009  
Publisher:  University of Central Florida  
Language(s):  English  
Abstract/Description:  Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A lineartime algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomialtime algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edgeface chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A wellknown result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.  
Identifier:  CFE0002507 (IID), ucf:47684 (fedora)  
Note(s): 
20090501 Ph.D. Sciences, Department of Mathematics Doctorate This record was generated from author submitted information. 

Subject(s): 
plane graphs graph coloring almost regular graphs 

Persistent Link to This Record:  http://purl.flvc.org/ucf/fd/CFE0002507  
Restrictions on Access:  private 20100101  
Host Institution:  UCF 