Date Thesis Awarded
5-2010
Access Type
Honors Thesis -- Access Restricted On-Campus Only
Degree Name
Bachelors of Science (BS)
Department
Mathematics
Advisor
Gexin Yu
Committee Members
Chi-Kwong Li
Christopher J. Abelt
Abstract
Many application problems can be phrased in terms of graph colorings. A defective coloring of a graph assigns colors to vertices so that a vertex can have at most one neighbor with the same color. We may further require the color classes of a defective coloring to have almost the same sizes, namely equitable-defective coloring. Take notice that a graph may have an equitable-defective t-coloring, but may not have an equitable-defective (t+1)-coloring. We study the equitable-defective coloring of sparse graphs. It is known that a planar graph with minimum degree at least 2 and girth at least 10 has an equitable (proper) t-coloring for any t ≥ 4. In this thesis, we show that under the same conditions, the graphs have an equitable defective 3-coloring as well.
Recommended Citation
Williams, Harold Lee II, "Equitable and Defective Coloring of Sparse Graphs" (2010). Undergraduate Honors Theses. William & Mary. Paper 676.
https://scholarworks.wm.edu/honorstheses/676
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Comments
Thesis is part of Honors ETD pilot project, 2008-2013. Migrated from Dspace in 2016.