A Lower Bound for Mixed Ramsey Numbers: Total Chromatic Number Versus Stars

Abstract

The total chromatic number ${\chi }_2(G)$ of a graph $G$ is the smallest number of colors which can be assigned to the vertices and edges of $G$ so that adjacent or incident elements are assigned different colors. For a positive integer $m$ and the star graph $K_{1,n}$, the mixed Ramsey number ${\chi }_2(m,K_{1,n})$ is the least positive integer $p$ such that if $G$ is any graph of order $p$, either ${\chi }_2(G)\ge m$ or the complement $\overline{G}$ contains $K_{1,n}$ as a subgraph.
In this paper, we introduce the concept of total chromatic matrix and use it to show the following lower bound: ${\chi }_2(m,K_{1,n})\ge m+n–2$ for $m\ge 3$ and $n\ge 1$. Combining this lower bound with the known upper bound (Fink), we obtain that ${\chi }_2(m,K_{1,n})=m+n–2$ for $m$ odd and $n$ even, and $m+n–2\le {\chi }_2(m,K_{1,n})\le m+n–1$ otherwise.