Volume 8
n° 1 (2006), pp. 159-172| author: | Kchikech, Mustapha and Togni, Olivier |
|---|---|
| title: | Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes |
| keywords: | Graph theory; Coloring; Multicoloring; Power graph; Product graph; Approximation algorithm; Greedy algorithm. |
| abstract: | A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infinite triangular mesh is an induced subgraph of the fourth power of the infinite square mesh and we present 2-approximation algorithms for multicoloring a power square mesh and the second power of a triangular mesh, 3-approximation algorithms for multicoloring powers of semi-toroidal meshes and of triangular meshes and 4-approximation algorithm for multicoloring the power of a toroidal mesh. We also give similar algorithms for the Cartesian product of powers of paths and of cycles. |
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | Kchikech, Mustapha and Togni, Olivier (2006), Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes, Discrete Mathematics and Theoretical Computer Science 8, pp. 159-172 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dm080110.ps.gz (125 K) |
| ps-source: | dm080110.ps (333 K) |
| pdf-source: | dm080110.pdf (269 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.
Automatically produced on Tue May 23 21:01:58 CEST 2006 by falk