Tınaz Ekim ; Bernard Ries ; Dominique De Werra - Split-critical and uniquely split-colorable graphs

dmtcs:484 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 5 - https://doi.org/10.46298/dmtcs.484
Split-critical and uniquely split-colorable graphsArticle

Authors: Tınaz Ekim ; Bernard Ries ORCID1,2; Dominique De Werra

  • 1 Centre for Discrete Mathematics and its Applications [Warwick]
  • 2 Warwick Business School

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.


Volume: Vol. 12 no. 5
Section: Graph and Algorithms
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: Split-coloring,split-critical,uniquely split-colorable,split-decreasing,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 365 times.
This article's PDF has been downloaded 443 times.