https://hal.inria.fr/hal-00972326Dereniowski, DariuszDariuszDereniowskiGdansk University of Technology - Department of Algorithms and Systems Modelling [ETI GUT] - ETI - Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] - GUT - Gdańsk University of TechnologyNadolski, AdamAdamNadolskiGdansk University of Technology - Department of Algorithms and Systems Modelling [ETI GUT] - ETI - Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] - GUT - Gdańsk University of TechnologyA note on compact and compact circular edge-colorings of graphsHAL CCSD2008[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Inria Sophia Antipolis-Méditerranée / I3s, Service Ist2014-04-03 16:13:212021-10-19 23:27:272014-04-03 16:39:43enJournal articleshttps://hal.inria.fr/hal-00972326/document10.46298/dmtcs.431application/pdf1We 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 a compact edge-coloring and that the decision problem of the existence of compact circular edge-coloring is NP-complete in general. Then we provide a polynomial time 1:5-approximation algorithm and pseudo-polynomial exact algorithm for compact circular coloring of odd cycles and prove that it is NP-hard to optimally color these graphs. Finally, we prove that if a path P2 is joined by an edge to an odd cycle then the problem of the existence of a compact circular coloring becomes NP-complete.