PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 95-102
Tytuł artykułu

Unique-Maximum Coloring Of Plane Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
1
Strony
95-102
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2014-09-23
poprawiono
2015-04-28
zaakceptowano
2015-04-28
online
2016-01-19
Twórcy
autor
  • Institute of Mathematics, P.J.Šafárik University in Košice, Slovakia
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1846
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.