%0 Journal Article
%T A note on compact and compact circular edge-colorings of graphs
%A Dariusz Dereniowski
%A Adam Nadolski
%J Discrete Mathematics & Theoretical Computer Science
%D 2008
%I Discrete Mathematics & Theoretical Computer Science
%X In the paper we study two variants of edge-coloring of edge-weighted graphs, namely compact edge-coloring and circular compact edge-coloring. First, we discuss relations between these two coloring models. We prove that every outerplanar bipartite graph admits compact edge-coloring and that the problem of the existence of compact circular edge-coloring is NP-complete in general. Then we provide a polynomial time 1.5-approximate algorithm and pseudo-polynomial time exact algorithm for compact circular coloring of odd cycles and prove that it is NP-hard to optimal color these graphs. Finally, we prove that if a path P_2 is attached to an odd cycle then the problem of the existence of a compact circular coloring becomes NP-complete.
%U http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/526