Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00258
The Black-and-White Coloring Problem on Chordal Graphs
Shira Zucker
Vol. 16, no. 2, pp. 261-281, 2012. Regular paper.
Abstract Given a graph G and positive integers b and w, the black-and-white coloring problem asks about the existence of a partial vertex-coloring of G, with b vertices colored black and w white, such that there is no edge between a black and a white vertex.
This problem is known to be NP-complete in general.
We provide here a polynomial time algorithm for chordal graphs.
|
Submitted: September 2009.
Reviewed: January 2011.
Revised: May 2011.
Reviewed: August 2011.
Revised: September 2011.
Accepted: February 2012.
Final: March 2012.
Published: March 2012.
Communicated by
Martin Fürer
|
Journal Supporters
|