Daniel Berend ; Ephraim Korach ; Shira Zucker - Two-anticoloring of planar and related graphs

dmtcs:3388 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3388
Two-anticoloring of planar and related graphs

Authors: Daniel Berend 1,2; Ephraim Korach 1,3; Shira Zucker 1,4

  • 1 Ben-Gurion University of the Negev
  • 2 Department of Mathematics [Be'er Sheva]
  • 3 Department of Industrial Engineering & Management [Be'er Sheva]
  • 4 Department of Computer Science [Beer-Sheva]

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.

https://doi.org/10.46298/dmtcs.3388
Source: HAL:hal-01184223v1
Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: separation,Graph,algorithm,combinatorial optimization,graph anticoloring,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 149 times.
This article's PDF has been downloaded 139 times.