Skip to Main content Skip to Navigation
Conference papers

Two-anticoloring of planar and related graphs

Abstract : 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.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184223
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 13, 2015 - 1:35:09 PM
Last modification on : Monday, July 22, 2019 - 11:42:05 AM
Long-term archiving on: : Saturday, November 14, 2015 - 10:24:46 AM

File

dmAD0130.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184223, version 1

Collections

Citation

Daniel Berend, Ephraim Korach, Shira Zucker. Two-anticoloring of planar and related graphs. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.335-342. ⟨hal-01184223⟩

Share

Metrics

Record views

341

Files downloads

827