logo_acta

Acta Mathematica Vietnamica

ON COLORINGS OF SPLIT GRAPHS

NGO DAC TAN, LE XUAN HUNG

Abstract

A graph $G = (V,E)$ is called a split graph if there exists a partition $V = I \cup K$ such that the subgraphs of $G$ induced by $I$ and $K$ are empty and complete graphs, respectively. In this paper, we determine chromatic polynomials for split graphs and characterize chromatically unique split graphs. Some sufficient conditions for split graphs to be Class one are also proved. In particular, we prove that the conjecture posed by Hilton and Zhao is true for split graphs.