Geodesic
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
Discrete mathematics & theoretical computer science, Tome 8 (2006).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2006_8_a12,
     author = {Kchikech, Mustapha and Togni, Olivier},
     title = {Approximation {Algorithms} for {Multicoloring} {Planar} {Graphs} and {Powers} of {Square} and {Triangular} {Meshes}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {8},
     year = {2006},
     doi = {10.46298/dmtcs.371},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.371/}
}
TY  - JOUR
AU  - Kchikech, Mustapha
AU  - Togni, Olivier
TI  - Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.371/
DO  - 10.46298/dmtcs.371
LA  - en
ID  - DMTCS_2006_8_a12
ER  - 
%0 Journal Article
%A Kchikech, Mustapha
%A Togni, Olivier
%T Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
%J Discrete mathematics & theoretical computer science
%D 2006
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.371/
%R 10.46298/dmtcs.371
%G en
%F DMTCS_2006_8_a12
Kchikech, Mustapha; Togni, Olivier. Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes. Discrete mathematics & theoretical computer science, Tome 8 (2006). doi : 10.46298/dmtcs.371. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.371/

Cité par Sources :