Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903053 | Discrete Mathematics | 2018 | 12 Pages |
Abstract
Given a nonnegative integer d and a positive integer k, a graph G is said to be (k,d)-colorable if the vertices of G can be colored with k colors such that every vertex has at most d neighbors receiving the same color as itself. Let â± be the family of planar graphs without 3-cycles adjacent to cycles of length 3 or 5. This paper proves that everyone in â± is (3,1)-colorable. This is the best possible in the sense that there are members in â± which are not (3,0)-colorable.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zhengke Miao, Yingqian Wang, Chuanni Zhang, Huajun Zhang,