On Split-Coloring Problems

Authors: Ekim, T.1; Werra, D.2

Source: Journal of Combinatorial Optimization, Volume 10, Number 3, November 2005 , pp. 211-225(15)

Publisher: Springer

Buy & download fulltext article:


Price: $47.00 plus tax (Refund Policy)


We study a new coloring concept which generalizes the classical vertex coloring problem in a graph by extending the notion of stable sets to split graphs. First of all, we propose the packing problem of finding the split graph of maximum size where a split graph is a graph G = (V,E) in which the vertex set V can be partitioned into a clique K and a stable set S. No condition is imposed on the edges linking vertices in S to the vertices in K. This maximum split graph problem gives rise to an associated partitioning problem that we call the split-coloring problem. Given a graph, the objective is to cover all his vertices by a least number of split graphs. Definitions related to this new problem are introduced. We mention some polynomially solvable cases and describe open questions on this area.

Keywords: packing; partitioning; split-coloring; vertex covering by split graphs

Document Type: Research Article

DOI: http://dx.doi.org/10.1007/s10878-005-4103-7

Affiliations: 1: Email: tinaz.ekim@epfl.ch 2: Email: dewerra.ima@epfl.ch

Publication date: November 1, 2005

Related content


Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page