On Split-Coloring Problems |
| |
Authors: | Email author" target="_blank">T?EkimEmail author D?de?Werra |
| |
Institution: | (1) Institute of Mathematics—ROSE, Ecole Polytechnique Fédérale de Lausanne, CH-1015 Lausanne-Ecublens, Switzerland |
| |
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.
An erratum to this article is available at . |
| |
Keywords: | split-coloring vertex covering by split graphs partitioning packing |
本文献已被 SpringerLink 等数据库收录! |