Unique-Maximum Coloring Of Plane Graphs

• Autorzy: Igor Fabrici , Frank Göring
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

plane graph; weak-parity coloring; unique-maximum coloring

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 95-102

Daty

wydano

2016-02-01

otrzymano

2014-09-23

poprawiono

2015-04-28

zaakceptowano

2015-04-28

online

2016-01-19

Twórcy

autor

Igor Fabrici

• Institute of Mathematics, P.J.Šafárik University in Košice, Slovakia

autor

Frank Göring

• Fakultät für Mathematik, Technische Universität Chemnitz, Germany

Bibliografia

• [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]
• [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]
• [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[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]
• [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]
• [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]
• [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[Crossref]
• [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]
• [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]
• [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]
• [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]
• [16] S. Smorodinsky, Conflict-free coloring and its applications. arXiv: 1005.3616.

Identyfikatory

DOI

10.7151/dmgt.1846