Mixed Ramsey Numbers: Harmonious Chromatic Number versus Independence Number

Abstract

The harmonious chromatic number of a graph $G$, denoted $h(G)$, is the smallest number of colors needed to color the vertices of $G$ so that adjacent vertices receive different colors and no two edges have the same pair of colors represented at their endvertices.The mixed harmonious Ramsey number $H(a,b)$ is defined to be the smallest integer $p$ such that if a graph $G$ has $p$ vertices, then either $h(G)\ge a$ or $\alpha (G)\ge b$. For certain values of $a$ and $b$, we determine the exact value of $H(a,b)$. In some other cases, we are able to determine upper and lower bounds for $H(a,b)$.