Geodesic
Two-anticoloring of planar and related graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

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

An $\textit{anticoloring}$ of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. We deal with the anticoloring problem with two colors for planar graphs, and, using Lipton and Tarjan's separation algorithm, provide an algorithm with some bound on the error. In the particular cases of graphs which are strong products of two paths or two cycles, we provide an explicit optimal solution. 
@article{DMTCS_2005_special_249_a36,
     author = {Berend, Daniel and Korach, Ephraim and Zucker, Shira},
     title = {Two-anticoloring of planar and related graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3388},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3388/}
}
TY  - JOUR
AU  - Berend, Daniel
AU  - Korach, Ephraim
AU  - Zucker, Shira
TI  - Two-anticoloring of planar and related graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3388/
DO  - 10.46298/dmtcs.3388
LA  - en
ID  - DMTCS_2005_special_249_a36
ER  - 
%0 Journal Article
%A Berend, Daniel
%A Korach, Ephraim
%A Zucker, Shira
%T Two-anticoloring of planar and related graphs
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3388/
%R 10.46298/dmtcs.3388
%G en
%F DMTCS_2005_special_249_a36
Berend, Daniel; Korach, Ephraim; Zucker, Shira. Two-anticoloring of planar and related graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3388. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3388/

Cité par Sources :