Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Semi-balanced colorings of graphs: Generalized 2-colorings based on a relaxed discrepancy condition

Jansson, Jesper LU and Tokuyama, T (2004) In Graphs and Combinatorics 20(2). p.205-222
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(nm(2)) time.
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Graphs and Combinatorics
volume
20
issue
2
pages
205 - 222
publisher
Springer
external identifiers
  • wos:000221884700006
  • scopus:4544357741
ISSN
0911-0119
DOI
10.1007/s00373-004-0557-0
language
English
LU publication?
yes
id
a3dd66f9-a030-4339-ac4f-598f88eaef89 (old id 275306)
date added to LUP
2016-04-01 15:24:46
date last changed
2022-04-14 22:02:56
@article{a3dd66f9-a030-4339-ac4f-598f88eaef89,
  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(nm(2)) time.}},
  author       = {{Jansson, Jesper and Tokuyama, T}},
  issn         = {{0911-0119}},
  language     = {{eng}},
  number       = {{2}},
  pages        = {{205--222}},
  publisher    = {{Springer}},
  series       = {{Graphs and Combinatorics}},
  title        = {{Semi-balanced colorings of graphs: Generalized 2-colorings based on a relaxed discrepancy condition}},
  url          = {{http://dx.doi.org/10.1007/s00373-004-0557-0}},
  doi          = {{10.1007/s00373-004-0557-0}},
  volume       = {{20}},
  year         = {{2004}},
}