|
|||||
|
|
Anticoloring and separation of graphs |
|
| Authors: | D Berend E Korach |
| Institution: | a Department of Mathematics, Ben-Gurion University, Beer Sheva 84105, Israel b Department of Computer Science, Ben-Gurion University, Beer Sheva 84105, Israel c Department of Industrial Engineering and Management, Ben-Gurion University, Beer Sheva 84105, Israel |
| Abstract: | An anticoloring of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. The anticoloring problem seeks, roughly speaking, such colorings with many vertices colored in each color. We deal with the anticoloring problem for planar graphs and, using Lipton and Tarjan’s separation algorithm, provide an algorithm with some bound on the error. We also show that, to solve the anticoloring problem for general graphs, it suffices to solve it for connected graphs. |
| Keywords: | Disconnected graph Algorithm Combinatorial optimization Graph anticoloring Separation Planar graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |