Daniel Berend
Senior Academic
A Reduction of the Anticoloring Problem to Connected Graphs
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.
| Publication language | English |
| Pages | 445-451 |
| Journal | Electronic Notes in Discrete Mathematics |
| Volume | 28 |
| Publication status | Published - 01.03.2007 |
Keywords
Graph
algorithm
combinatorial optimization
disconnected graph
graph anticoloring
ASJC Scopus subject areas
Discrete Mathematics and Combinatorics
Applied Mathematics
