Note on Antipodal (Hamiltonian) Chromatic Number of Paths

被引:0
作者
Shen, Yufa [1 ]
Chen, Zuoli [1 ]
Zhang, Lingmin [1 ]
Guo, Jun
机构
[1] Hebei Normal Univ Sci & Technol, Dept Math, Qinhuangdao 066004, Peoples R China
来源
PROCEEDINGS OF THE NINTH INTERNATIONAL CONFERENCE ON INFORMATION AND MANAGEMENT SCIENCES | 2010年 / 9卷
关键词
Radio colorings; Antipodal chromatic number; Hamiltonian chromatic number; Paths; COLORINGS;
D O I
暂无
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
For paths P-n, Khennoufa and Togni gave that ac(P-n) = 2p(2) - 2p + 3 if n = 2p + 1, and ac(P-n) = 2p(2) - 4p+5 if n = 2p, which disproved a conjecture posed by Chartrand, Erwin and Zhang, for antipodal chromatic number of Pn for all integer n >= 7. In this paper, by an in-depth analysis, we show that the result of Khennoufa and Togni is true, but their proof for the case n = 2p is not correct, and present a corrective proof for the result ac(P-n) = 2p(2) - 4p + 5 if n = 2p. As the hamiltonian chromatic number of P-n is equal to ac(P-n), the result of this paper also gives the exact value of hamiltonian chromatic number of P-n.
引用
收藏
页码:503 / 506
页数:4
相关论文
共 12 条
[1]   On hamiltonian colorings of graphs [J].
Chartrand, G ;
Nebesky, L ;
Zhang, P .
DISCRETE MATHEMATICS, 2005, 290 (2-3) :133-143
[2]  
Chartrand G., 2004, Discussiones Mathematicae Graph Theory, V24, P5, DOI 10.7151/dmgt.1209
[3]   Hamiltonian colorings of graphs [J].
Chartrand, G ;
Nebesky, L ;
Zhang, P .
DISCRETE APPLIED MATHEMATICS, 2005, 146 (03) :257-272
[4]  
Chartrand G., 2002, Math. Bohem, V127, P57, DOI [10.21136/MB.2002.133978, DOI 10.21136/MB.2002.133978]
[5]  
Chartrand G., 2001, Bull Inst Combin Appl, V33, P77
[6]  
Chartrand G., 2005, Bull. Inst. Comb. Appl., V43, P43
[7]  
Fotakis D., 1999, Networks in Distributed Computing. DIMACS Workshop, P73
[8]  
Khennoufa R, 2005, MATH BOHEM, V130, P277
[9]   Multilevel distance labelings for paths and cycles [J].
Liu, DDF ;
Zhu, XD .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (03) :610-621
[10]   On hamiltonian colorings for some graphs [J].
Shen, Yufa ;
He, Wenjie ;
Li, Xue ;
He, Donghong ;
Yang, Xiaojing .
DISCRETE APPLIED MATHEMATICS, 2008, 156 (15) :3028-3034