Split-critical and uniquely split-colorable graphs

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (5), pp.1-24
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990427
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:36:20
Dernière modification le : mercredi 29 novembre 2017 - 10:26:20
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:13:40

Fichier

1479-5705-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990427, version 1

Collections

Citation

Tınaz Ekim, Bernard Ries, Dominique De Werra. Split-critical and uniquely split-colorable graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (5), pp.1-24. 〈hal-00990427〉

Partager

Métriques

Consultations de la notice

76

Téléchargements de fichiers

191