Geodesic
On harmonious colouring of trees
The electronic journal of combinatorics, Tome 19 (2012) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $G$ be a simple graph and $\Delta(G)$ denote the maximum degree of $G$. A harmonious colouring of $G$ is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number $h(G)$ is the least number of colours in such a colouring. In this paper it is shown that if $T$ is a tree of order $n$ and $\Delta(T)\geq\frac{n}{2}$, then there exists a harmonious colouring of $T$ with $\Delta(T)+1$ colours such that every colour is used at most twice. Thus $h(T)=\Delta(T)+1$. Moreover, we prove that if $T$ is a tree of order $n$ and $\Delta(T) \le \Big\lceil\frac{n}{2}\Big\rceil$, then there exists a harmonious colouring of $T$ with $\Big\lceil \frac{n}{2}\Big \rceil +1$ colours such that every colour is used at most twice. Thus $h(T)\leq \Big\lceil \frac{n}{2} \Big\rceil +1$.
DOI : 10.37236/9
Classification : 05C15, 05C05, 05C10
Mots-clés : harmonious chromatic number 
@article{10_37236_9,
     author = {A. Aflaki and S. Akbari and K.J. Edwards and D.S. Eskandani and M. Jamaali and H. Ravanbod},
     title = {On harmonious colouring of trees},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {1},
     doi = {10.37236/9},
     zbl = {1244.05083},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9/}
}
TY  - JOUR
AU  - A. Aflaki
AU  - S. Akbari
AU  - K.J. Edwards
AU  - D.S. Eskandani
AU  - M. Jamaali
AU  - H. Ravanbod
TI  - On harmonious colouring of trees
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9/
DO  - 10.37236/9
ID  - 10_37236_9
ER  - 
%0 Journal Article
%A A. Aflaki
%A S. Akbari
%A K.J. Edwards
%A D.S. Eskandani
%A M. Jamaali
%A H. Ravanbod
%T On harmonious colouring of trees
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9/
%R 10.37236/9
%F 10_37236_9
A. Aflaki; S. Akbari; K.J. Edwards; D.S. Eskandani; M. Jamaali; H. Ravanbod. On harmonious colouring of trees. The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/9

Cité par Sources :