Semi-Balanced Colorings of Graphs: Generalized 2-Colorings Based on a Relaxed Discrepancy Condition |
| |
Authors: | Email author" target="_blank">Jesper?JanssonEmail author Takeshi?Tokuyama |
| |
Institution: | (1) Department of Computer Science, Lund University, 118, 221 00 Lund, Sweden;(2) Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan |
| |
Abstract: | We generalize the concept of a 2-coloring of a graph to what we call a semi-balanced coloring by relaxing a certain discrepancy condition on the shortest-paths hypergraph of the graph. Let G be an undirected, unweighted, connected graph with n vertices and m edges. We prove that the number of different semi-balanced colorings of G is: (1) at most n+1 if G is bipartite; (2) at most m if G is non-bipartite and triangle-free; and (3) at most m+1 if G is non-bipartite. Based on the above combinatorial investigation, we design an algorithm to enumerate all semi-balanced colorings of G in O(nm2) time.Acknowledgments The authors thank Tetsuo Asano, Naoki Katoh, Kunihiko Sadakane, and Hisao Tamaki for helpful discussions and comments.Supported in part by Sweden-Japan FoundationFinal version received: November 17, 2003 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|