A Reduction of the Anticoloring Problem to Connected Graphs |
| |
Institution: | 1. Science and Technology Park TecnoTam, Cinvestav Tamaulipas, Victoria 87130, Mexico;2. Universidad Autonoma de Tamaulipas, Matamoros 8 y 9, Victoria 87000, Mexico |
| |
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, for such colorings with many vertices colored in each color. We show that, to solve the anticoloring problem with two colors for general graphs, it suffices to solve it for connected graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|