Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jda.2011.03.005 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
unique-maximum coloring,conflict-free coloring,vertex colorings,chromatic number,graph unique-maximum,maximum color,computational complexity aspect,grid graph,conflict-free colorings,completeness result,unique-maximum colorings | Journal | 9 |
Issue | ISSN | ISBN |
3 | 0302-9743 | 3-642-13072-0 |
Citations | PageRank | References |
4 | 0.43 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Cheilaris | 1 | 55 | 8.19 |
| Géza Tóth | 2 | 581 | 55.60 |