Geodesic
The Black-and-White Coloring Problem on Chordal Graphs
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 261-281.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00258
Keywords: graph algorithm, Black-and-White coloring, anticoloring problem, chordal graphs, split graphs 
@article{JGAA_2012_16_2_a5,
     author = {Shira Zucker},
     title = {The {Black-and-White} {Coloring} {Problem} on {Chordal} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {261--281},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00258},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00258/}
}
TY  - JOUR
AU  - Shira Zucker
TI  - The Black-and-White Coloring Problem on Chordal Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 261
EP  - 281
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00258/
DO  - 10.7155/jgaa.00258
LA  - en
ID  - JGAA_2012_16_2_a5
ER  - 
%0 Journal Article
%A Shira Zucker
%T The Black-and-White Coloring Problem on Chordal Graphs
%J Journal of Graph Algorithms and Applications
%D 2012
%P 261-281
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00258/
%R 10.7155/jgaa.00258
%G en
%F JGAA_2012_16_2_a5
Shira Zucker. The Black-and-White Coloring Problem on Chordal Graphs. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 261-281. doi : 10.7155/jgaa.00258. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00258/

Cité par Sources :