Unique-Maximum Coloring Of Plane Graphs

Igor Fabrici; Frank Göring

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 95-102
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Igor Fabrici, and Frank Göring. "Unique-Maximum Coloring Of Plane Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 95-102. <http://eudml.org/doc/276968>.

@article{IgorFabrici2016,
abstract = {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.},
author = {Igor Fabrici, Frank Göring},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {plane graph; weak-parity coloring; unique-maximum coloring},
language = {eng},
number = {1},
pages = {95-102},
title = {Unique-Maximum Coloring Of Plane Graphs},
url = {http://eudml.org/doc/276968},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Igor Fabrici
AU - Frank Göring
TI - Unique-Maximum Coloring Of Plane Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 95
EP - 102
AB - 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.
LA - eng
KW - plane graph; weak-parity coloring; unique-maximum coloring
UR - http://eudml.org/doc/276968
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). 
  2. [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] Zbl1135.05020
  3. [3] P. Cheilaris, Conflict-Free Coloring, PhD Thesis (City University of New York, 2009). 
  4. [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] Zbl1292.05107
  5. [5] P. Cheilaris, E. Specker and S. Zachos, Neochromatica, Comment. Math. Univ. Carolin. 51 (2010) 469–480. Zbl1224.05164
  6. [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. [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] Zbl1193.05065
  8. [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] Zbl1069.68120
  9. [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] Zbl1311.05061
  10. [10] R. Glebov, T. Szabó and G. Tardos, Conflict-free coloring of graphs. arXiv: 1111.5501. Zbl1288.05086
  11. [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] Zbl0842.05032
  12. [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] Zbl1247.05082
  13. [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] Zbl1029.05057
  14. [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] Zbl1197.05054
  15. [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] Zbl1032.05050
  16. [16] S. Smorodinsky, Conflict-free coloring and its applications. arXiv: 1005.3616. Zbl1314.05081

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.