Article ID Journal Published Year Pages File Type
8903053 Discrete Mathematics 2018 12 Pages PDF
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
, , , ,