2009/12/15 by Panagiotis Cheilaris, Geza Toth, Cheilaris, Panagiotis +1
Computer Science · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.0912.3004
arxiv created 2009/12/15 · arxiv updated 2010/01/14
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.