Split-critical and uniquely split-colorable graphs
Tınaz Ekim, Bernard Ries, Dominique de Werra
Abstract
The split-coloring problem is a generalized vertex coloring problem
where we partition the vertices into a minimum number of split graphs.
In this paper, we study some notions which are extensively studied for
the usual vertex coloring and the cocoloring problem from the point of
view of split-coloring, such as criticality and the uniqueness of the
minimum split-coloring. We discuss some properties of split-critical
and uniquely split-colorable graphs. We describe constructions of such
graphs with some additional properties. We also study the effect of
the addition and the removal of some edge sets on the value of the
split-chromatic number. All these results are compared with their
cochromatic counterparts. We conclude with several research directions
on the topic.
Full Text: PDF PostScript