Geodesic
Unique-Maximum Coloring Of Plane Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 95-102.

Voir la notice de l'article provenant de la source Library of Science

A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . ., k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.
Keywords: plane graph, weak-parity coloring, unique-maximum coloring 
@article{DMGT_2016_36_1_a6,
     author = {Fabrici, Igor and G\"oring, Frank},
     title = {Unique-Maximum {Coloring} {Of} {Plane} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {95--102},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a6/}
}
TY  - JOUR
AU  - Fabrici, Igor
AU  - Göring, Frank
TI  - Unique-Maximum Coloring Of Plane Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 95
EP  - 102
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a6/
LA  - en
ID  - DMGT_2016_36_1_a6
ER  - 
%0 Journal Article
%A Fabrici, Igor
%A Göring, Frank
%T Unique-Maximum Coloring Of Plane Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 95-102
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a6/
%G en
%F DMGT_2016_36_1_a6
Fabrici, Igor; Göring, Frank. Unique-Maximum Coloring Of Plane Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 95-102. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a6/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[2] D.P. Bunde, K. Milans, D.B. West and H. Wu, Parity and strong parity edge-coloring of graphs, Congr. Numer. 187 (2007) 193–213.

[3] P. Cheilaris, Conflict-Free Coloring, PhD Thesis (City University of New York, 2009).

[4] P. Cheilaris, B. Keszegh and D. Pálvölgyi, Unique-maximum and conflict-free colouring for hypergraphs and tree graphs, SIAM J. Discrete Math. 27 (2013) 1775–1787. doi:10.1137/120880471

[5] P. Cheilaris, E. Specker and S. Zachos, Neochromatica, Comment. Math. Univ. Carolin. 51 (2010) 469–480.

[6] P. Cheilaris and G. Tóth, Graph unique-maximum and conflict-free colouring, J. Discrete Algorithms 9 (2011) 241–251. doi:10.1016/j.jda.2011.03.005

[7] J. Czap and S. Jendrol’, Colouring vertices of plane graphs under restrictions given by faces, Discuss. Math. Graph Theory 29 (2009) 521–543. doi:10.7151/dmgt.1462

[8] G. Even, Z. Lotker, D. Ron and S. Smorodinsky, Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks, SIAM J. Comput. 33 (2003) 94–136. doi:10.1137/S0097539702431840

[9] I. Fabrici, S. Jendrol’ and M. Vrbjarová, Unique-maximum edge-colouring of plane graphs with respect to faces, Discrete Appl. Math. 185 (2015) 239–243. doi:10.1016/j.dam.2014.12.002

[10] R. Glebov, T. Szabó and G. Tardos, Conflict-free coloring of graphs . arXiv: 1111.5501.

[11] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141–154. doi:10.1016/0012-365X(93)E0216-Q

[12] A.V. Kostochka, M. Kumbhat and T. Łuczak, Conflict-free colorings of uniform hypergraphs with few edges, Combin. Probab. Comput. 21 (2012) 611–622. doi:10.1017/S0963548312000156

[13] A. Kündgen and R. Ramamurthi, Coloring face-hypergraphs of graphs on surfaces, J. Combin. Theory Ser. B 85 (2002) 307–337. doi:10.1006/jctb.2001.2107

[14] J. Pach and G. Tardos, Conflict-free colorings of graphs and hypergraphs, Combin. Probab. Comput. 18 (2009) 819–834. doi:10.1017/S0963548309990290

[15] R. Ramamurthi and D.B. West, Maximum face-constrained coloring of plane graphs, Discrete Math. 274 (2004) 233–240. doi:10.1016/j.disc.2003.09.001

[16] S. Smorodinsky, Conflict-free coloring and its applications . arXiv: 1005.3616.