#### Date Thesis Awarded

12-2016

#### Document Type

Honors Thesis

#### Degree Name

Bachelors of Science (BS)

#### Department

Mathematics

#### Advisor

Gexin Yu

#### Committee Member

Chi-Kwong Li

#### Committee Member

Joshua Erlich

#### Abstract

A graph G is (d_1,d_2,… ,d_t)-colorable if its vertices may be partitioned into subsets V_1,V_2,...,V_t such that for each i, the maximum degree of the subgraph induced by V_i is at most d_i. We study this relaxed coloring of graphs with bounded maximum average degrees. Specifically, we use discharging and other methods to seek new upper and lower bounds for the maximum average degree of (1,1,0)-colorable graphs. We generalize this result to colorings of the type (1_1,1_2,...,1_a,0_1,...,0_b), improving the results by Dorbec, Kaiser, Montassier, and Raspaud (J. of Graph Theory, 2014) for a large class of colorings.

#### Recommended Citation

Kopreski, Michael C., "Relaxed Coloring of Sparse Graphs" (2016). *Undergraduate Honors Theses.* Paper 1002.

http://publish.wm.edu/honorstheses/1002

#### Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 License.