Date Thesis Awarded

5-2010

Document Type

Honors Thesis

Degree Name

Bachelors of Science (BS)

Department

Mathematics

Advisor

Gexin Yu

Committee Member

Chi-Kwong Li

Committee Member

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.

Creative Commons License

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.

Share

COinS