Maximum average degree and relaxed coloring |
| |
Authors: | Michael Kopreski Gexin Yu |
| |
Affiliation: | Department of Mathematics, The College of William and Mary, Williamsburg, VA, 23185, USA |
| |
Abstract: | We say a graph is -colorable with of ’s and of ’s if may be partitioned into independent sets and sets whose induced graphs have maximum degree at most . The maximum average degree, , of a graph is the maximum average degree over all subgraphs of . In this note, for nonnegative integers , we show that if , then is -colorable. |
| |
Keywords: | Relaxed coloring Maximum average degree Global discharging |
本文献已被 ScienceDirect 等数据库收录! |
|