%0 Conference Paper %1 CFK+01b %A Caragiannis, I. %A Ferreira, A. %A Kaklamanis, C. %A Pérenne, S. %A Persiano, P. %A Rivano, H. %B 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'01) %C Boltenhagen, Germany %D 2001 %I Springer-Verlag %K Perso coloring %P 21--31 %T Approximate Constrained Bipartite Edge Coloring %V 2204 %X We study the following Constrained Bipartite Edge Coloring (CBEC) problem: We are given a bipartite graph G(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard event for bipartite graphs of maximum degree three 5.

@inproceedings{CFK+01b, abstract = {We study the following Constrained Bipartite Edge Coloring (CBEC) problem: We are given a bipartite graph G(U,V,E) of maximum degree l with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard event for bipartite graphs of maximum degree three [5].}, added-at = {2009-08-07T13:37:48.000+0200}, address = {Boltenhagen, Germany}, author = {Caragiannis, I. and Ferreira, A. and Kaklamanis, C. and P{\'e}renne, S. and Persiano, P. and Rivano, H.}, biburl = {https://www.bibsonomy.org/bibtex/29db080706cdb99f7e501408eddda896c/herverivano}, booktitle = {27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'01)}, date-added = {2009-08-07 13:05:23 +0200}, date-modified = {2009-08-07 13:29:11 +0200}, description = {Ma biblio}, interhash = {0468128a9a16a34690823326a8527554}, intrahash = {9db080706cdb99f7e501408eddda896c}, keywords = {Perso coloring}, month = {June}, pages = {21--31}, pdf = {ftp://ftp-sop.inria.fr/mascotte/Herve.Rivano/Biblio/cfk01b.pdf}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, timestamp = {2009-08-21T11:11:05.000+0200}, title = {Approximate Constrained Bipartite Edge Coloring}, volume = 2204, year = 2001 }