Keywords

plane graphs, graph coloring, almost regular graphs

Abstract

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.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

2009

Advisor

Zhao, Yue

Degree

Doctor of Philosophy (Ph.D.)

College

College of Sciences

Department

Mathematics

Degree Program

Mathematics

Format

application/pdf

Identifier

CFE0002507

URL

http://purl.fcla.edu/fcla/etd/CFE0002507

Language

English

Release Date

January 2010

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Download

Included in

Mathematics Commons

Share

COinS