You are here

UCF Digital Collections ยป ETD Collection

ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS

Download pdf | Full Screen View

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 linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face 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 well-known 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.
30 views
18 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 linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face 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 well-known 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): 2009-05-01
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 2010-01-01
Host Institution: UCF

In Collections