Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Two-anticoloring of ...
Conference paper

Two-anticoloring of planar and related graphs

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]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Proceedings
DOI
10.46298/dmtcs.3388
License
https://about.hal.science/hal-authorisation-v1
Indicators
593
Views
514
Downloads

Two-anticoloring of planar and related graphs

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]
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.
Keywords
  • [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]
  • Graph
  • algorithm
  • combinatorial optimization
  • graph anticoloring
  • separation
Cited by

Source: OpenCitations

  • Computing Maximum Matchings in Temporal Graphs

    SSRN Electronic Journal

    Authors : George B. Mertzios ORCID, Hendrik Molter ORCID, Rolf Niedermeier ORCID, Viktor Zamaraev ORCID, Philipp Zschoche ORCID

    Journal reference : Volume , 2022, pp.

    DOI : 10.2139/ssrn.4117558

  • Anticoloring of the rook’s graph

    Discrete Applied Mathematics

    Authors : Daniel Berend ORCID, Ephraim Korach, Orly Yahalom

    Journal reference : Volume 188, 2015, pp. 1-15

    DOI : 10.1016/j.dam.2015.02.023

  • Tabu search for the BWC problem

    Journal of Global Optimization

    Authors : Daniel Berend ORCID, Ephraim Korach, Shira Zucker

    Journal reference : Volume 54, 2011, pp. 649-667

    DOI : 10.1007/s10898-011-9783-1

  • On the local metric dimension of dipyramidal graph and king graph

    AIP conference proceedings

    Authors : Javas Alfreda Belva Yoga Pratama, Tri Atmojo Kusmayadi ORCID

    Journal reference : Volume 2326, 2021, pp. 020018

    DOI : 10.1063/5.0039319

  • Neighbor Sum Patterns: Chessboards to Toroidal Worlds

    American Mathematical Monthly

    Authors : Sayan Dutta ORCID, Ayanava Mandal, Sohom Gupta, Sourin Chatterjee ORCID

    Journal reference : Volume 133, 2025, pp. 13-34

    DOI : 10.1080/00029890.2025.2574832
Preview
Loading PDF preview...