Indexed by:
Abstract:
Let G be a graph of maximum degree Delta. A proper vertex coloring of G is acyclic if there is no bichromatic cycle. It was proved by Alon et al. [Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277-288] that G admits an acyclic coloring with O(Delta(4/3)) colors and a proper coloring with O(Delta((k-1)/(k-2))) colors such that no path with k vertices is bichromatic for a fixed integer k a parts per thousand yen 5. In this paper, we combine above two colorings and show that if k a parts per thousand yen 5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Delta((k-1)/(k-2))) colors such that no path with k vertices is bichromatic.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
FRONTIERS OF MATHEMATICS IN CHINA
ISSN: 1673-3452
Year: 2015
Issue: 6
Volume: 10
Page: 1343-1354
0 . 4 4 4
JCR@2015
0 . 8 0 0
JCR@2023
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 5
SCOPUS Cited Count: 5
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 6
Affiliated Colleges: