Semester

Summer

Date of Graduation

2001

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Hong-Jian Lai.

Abstract

In this dissertation, we introduce and study the idea of a dynamic coloring of a graph, a coloring in which any multiple-degree vertex of the graph must be adjacent to at least two color classes.;As parts of the overall research, we study (for some interesting subjects of colorings) the corresponding subjects of dynamic colorings, we compare the chromatic number and dynamic chromatic number, and we study some problems unique to dynamic colorings. Also, we introduce and briefly study a generalization of dynamic coloring.;The interesting subjects of colorings we consider are the chromatic number of important graphs, upper bounds of the chromatic number, vertex-critical graphs, and stable graphs. For these first three subjects, we prove theorems for dynamic colorings that are similar to important theorems known for proper colorings, while we show no such theorems exist for stable graphs.;We make an extensive comparison of the two chromatic numbers that includes a description of graphs for which the two chromatic numbers are equal, that presents a class of graphs for which the per-graph differences in the two chromatic numbers is unbounded, that shows the difference is at most two for any K1,3-free graph, and that studies the difference for regular graphs.;In our study of some unique problems of dynamic colorings, we characterize the graphs for which the dynamic chromatic number equals the number of vertices, we characterize the graphs for which the dynamic chromatic number equals one less than the number of vertices, we characterize the graphs for which the deletion of some vertex causes the dynamic chromatic number to decrease by more than one, and we obtain strong results describing graphs for which the removal of any vertex causes the dynamic chromatic number to increase.;Finally, we introduce and briefly study a generalization of dynamic coloring.

Download

Share

COinS