A note on compact and compact circular edge-colorings of graphs
Dariusz Dereniowski, Adam Nadolski
Abstract
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.
Full Text: PDF PostScript