Graph unique-maximum and conflict-free colorings

被引：28

作者：

Cheilaris, Panagiotis ^{[1
]}

Toth, Geza ^{[2
]}

机构：

[1] Ben Gurion Univ Negev, Ctr Adv Studies Math, POB 653, IL-84105 Beer Sheva, Israel

[2] Hungarian Acad Sci, Alfred Renyi Inst, H-1053 Budapest, Hungary

来源：

JOURNAL OF DISCRETE ALGORITHMS | 2011年 / 9卷 / 03期

关键词：

Conflict-free coloring; Unique-maximum coloring; Grid graph; Ordered coloring; Vertex ranking;

D O I：

10.1016/j.jda.2011.03.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We investigate the relationship between two kinds of vertex colorings of graphs: uniquemaximum 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. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：241 / 251

页数：11

共 17 条

[1]

Bar-Noy Amotz, 2009, Structural Information and Communication Complexity. 16th International Colloquium, SIROCCO 2009. Revised Selected Papers, P30

[2] Deterministic Conflict-Free Coloring for Intervals: From Offline to Online [J].

Bar-Noy, Amotz ;

Cheilaris, Panagiotis ;

Smorodinsky, Shakhar .

ACM TRANSACTIONS ON ALGORITHMS, 2008, 4 (04)

[3] Rankings of graphs [J].

Bodlaender, HL ;

Deogun, JS ;

Jansen, K ;

Kloks, T ;

Kratsch, D ;

Muller, H ;

Tuza, Z .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1998, 11 (01) :168-181

[4] APPROXIMATING TREEWIDTH, PATHWIDTH, FRONTSIZE, AND SHORTEST ELIMINATION TREE [J].

BODLAENDER, HL ;

GILBERT, JR ;

HAFSTEINSSON, H ;

KLOKS, T .

JOURNAL OF ALGORITHMS, 1995, 18 (02) :238-255

[5] Online conflict-free coloring for intervals [J].

Chen, Ke ;

Fiat, Amos ;

Kaplan, Haim ;

Levy, Meital ;

Matousek, Jiri ;

Mossel, Elchanan ;

Pach, Janos ;

Sharir, Micha ;

Smorodinsky, Shakhar ;

Wagner, Uli ;

Welzl, Emo .

SIAM JOURNAL ON COMPUTING, 2006, 36 (05) :1342-1359

[6]

Elbassioni K, 2006, LECT NOTES COMPUT SC, V3884, P254

[7] Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks [J].

Even, G ;

Lotker, Z ;

Ron, D ;

Smorodinsky, S .

SIAM JOURNAL ON COMPUTING, 2003, 33 (01) :94-136

[8] Conflict-free coloring of points and simple regions in the plane [J].

Har-Peled, S ;

Smorodinsky, S .

DISCRETE & COMPUTATIONAL GEOMETRY, 2005, 34 (01) :47-70

[9] OPTIMAL NODE RANKING OF TREES [J].

IYER, AV ;

RATLIFF, HD ;

VIJAYAN, G .

INFORMATION PROCESSING LETTERS, 1988, 28 (05) :225-229

[10] ORDERED COLORINGS [J].

KATCHALSKI, M ;

MCCUAIG, W ;

SEAGER, S .

DISCRETE MATHEMATICS, 1995, 142 (1-3) :141-154

← 1 2 →