Two-anticoloring of planar and related graphs
| Autor: | Daniel Berend, Ephraim Korach, Shira Zucker |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2005 |
| Předmět: |
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] Mathematics QA1-939 |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AD,..., Iss Proceedings (2005) |
| Druh dokumentu: | article |
| ISSN: | 1365-8050 |
| DOI: | 10.46298/dmtcs.3388 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|