Back to search

Central Florida

Almost Regular Graphs And Edge Face Colorings Of Plane Graphs

Abstract

dc:description.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.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Macon, Lisa
Contributors dc:contributor
  • Zhao, Yue

Subjects

dc:subject × 4

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
CFE0002507

Chain of custody

source
Harvested from
Central Florida
Base URL
stars.library.ucf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Macon, Lisa. Almost Regular Graphs And Edge Face Colorings Of Plane Graphs. https://stars.library.ucf.edu/etd/3923