Harmonious coloring of trees with large maximum degree

Cited 4 time in webofscience Cited 0 time in scopus
  • Hit : 60
  • Download : 0
A harmonious coloring of G is a proper vertex coloring of G such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of G, h(G), is the minimum number of colors needed for a harmonious coloring of G. We show that if T is a forest of order n with maximum degree Delta(T) >= n+2/3, then h(T) = {Delta(T) + 2, if T has non-adjacent vertices of degree Delta(T); Delta(T) + 1, otherwise. Moreover, the proof yields a polynomial-time algorithm for an optimal harmonious coloring of such a forest. (C) 2012 Elsevier B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2012-05
Language
English
Article Type
Article
Citation

DISCRETE MATHEMATICS, v.312, no.10, pp.1633 - 1637

ISSN
0012-365X
DOI
10.1016/j.disc.2012.02.009
URI
http://hdl.handle.net/10203/263355
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 4 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0