DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

Two-anticoloring of planar and related graphs

Daniel Berend, Ephraim Korach, Shira Zucker


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

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional