Semi-balanced colorings of graphs: Generalized 2-colorings based on a relaxed discrepancy condition
(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:
https://lup.lub.lu.se/record/275306
- author
- Jansson, Jesper LU and Tokuyama, T
- organization
- publishing date
- 2004
- 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}}, }