Date Thesis Awarded

12-2016

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

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. William & Mary. Paper 1002.
https://scholarworks.wm.edu/honorstheses/1002