Graph unique-maximum and conflict-free colorings

Details Graph unique-maximum and conflict-free colorings Graph unique-maximum and conflict-free colorings

2009-12-15

arxiv.org/abs/0912.3004v1

Computer Science

Discrete Mathematics

Scientific paper

We investigate the relationship between two kinds of vertex colorings of graphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every path of the graph the maximum color appears only once. In a conflict-free coloring, in every path of the graph there is a color that appears only once. We also study computational complexity aspects of conflict-free colorings and prove a completeness result. Finally, we improve lower bounds for those chromatic numbers of the grid graph.

Affiliated with

Also associated with

No associations

Rating

Graph unique-maximum and conflict-free colorings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph unique-maximum and conflict-free colorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph unique-maximum and conflict-free colorings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-48159