Split-critical and uniquely split-colorable graphs
Link to item filehttp://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1479/3367
DeweyPrincipes généraux des mathématiques
SujetSplit-coloring; split-critical; uniquely split-colorable; split-decreasing
Journal issueDiscrete Mathematics and Theoretical Computer Science
MetadataShow full item record
de Werra, Dominique
Abstract (EN)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.
Showing items related by title, author, creator and subject.
Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations Isaac, Yoann; Barthélemy, Quentin; Gouy-Pailler, Cédric; Sebag, Michèle; Atif, Jamal (2017) Article accepté pour publication ou publié
Waxin, Timothée (2011) Communication / Conférence
Paschos, Vangelis; Monnot, Jérôme; Escoffier, Bruno; Demange, Marc; de Werra, Dominique (2009) Article accepté pour publication ou publié