Dariusz Dereniowski ; Adam Nadolski - A note on compact and compact circular edge-colorings of graphs

dmtcs:431 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 3 - https://doi.org/10.46298/dmtcs.431
A note on compact and compact circular edge-colorings of graphsArticle

Authors: Dariusz Dereniowski 1; Adam Nadolski 1

  • 1 Department of Algorithms and Systems Modelling [ETI GUT]

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 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.


Volume: Vol. 10 no. 3
Section: Graph and Algorithms
Published on: January 1, 2008
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 303 times.
This article's PDF has been downloaded 435 times.