On Split-Coloring Problems
Source: Journal of Combinatorial Optimization, Volume 10, Number 3, November 2005 , pp. 211-225(15)
Abstract: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.
Document Type: Research Article
Publication date: November 1, 2005