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.
@article{bwmeta1.element.doi-10_7151_dmgt_1846,
author = {Igor Fabrici and Frank G\"oring},
title = {Unique-Maximum Coloring Of Plane Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {95-102},
zbl = {1329.05106},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1846}
}
Igor Fabrici; Frank Göring. Unique-Maximum Coloring Of Plane Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 95-102. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1846/
[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.[WoS] | Zbl 1135.05020
[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[Crossref][WoS] | Zbl 1292.05107
[5] P. Cheilaris, E. Specker and S. Zachos, Neochromatica, Comment. Math. Univ. Carolin. 51 (2010) 469–480. | Zbl 1224.05164
[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[Crossref]
[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[Crossref] | Zbl 1193.05065
[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[Crossref] | Zbl 1069.68120
[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[Crossref][WoS] | Zbl 1311.05061
[10] R. Glebov, T. Szabó and G. Tardos, Conflict-free coloring of graphs. arXiv: 1111.5501. | Zbl 1288.05086
[11] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141–154. doi:10.1016/0012-365X(93)E0216-Q[Crossref] | Zbl 0842.05032
[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[Crossref] | Zbl 1247.05082
[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[Crossref] | Zbl 1029.05057
[14] J. Pach and G. Tardos, Conflict-free colorings of graphs and hypergraphs, Combin. Probab. Comput. 18 (2009) 819–834. doi:10.1017/S0963548309990290[Crossref] | Zbl 1197.05054
[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[Crossref] | Zbl 1032.05050
[16] S. Smorodinsky, Conflict-free coloring and its applications. arXiv: 1005.3616. | Zbl 1314.05081