A note on face coloring entire weightings of plane graphs

Stanislav Jendrol; Peter Šugerek

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 2, page 421-426
  • ISSN: 2083-5892

Abstract

top
Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3

How to cite

top

Stanislav Jendrol, and Peter Šugerek. "A note on face coloring entire weightings of plane graphs." Discussiones Mathematicae Graph Theory 34.2 (2014): 421-426. <http://eudml.org/doc/267708>.

@article{StanislavJendrol2014,
abstract = {Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face \_ and also the weight of \_. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and \_ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3},
author = {Stanislav Jendrol, Peter Šugerek},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {entire weighting; plane graph; face colouring},
language = {eng},
number = {2},
pages = {421-426},
title = {A note on face coloring entire weightings of plane graphs},
url = {http://eudml.org/doc/267708},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Stanislav Jendrol
AU - Peter Šugerek
TI - A note on face coloring entire weightings of plane graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 2
SP - 421
EP - 426
AB - Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3
LA - eng
KW - entire weighting; plane graph; face colouring
UR - http://eudml.org/doc/267708
ER -

References

top
  1. [1] L. Addario-Berry, K. Dalal, C. McDiarmid, B.A. Reed and A. Thomason, Vertexcolouring edge-weightings, Combinatorica 27 (2007) 1-12. doi:10.1007/s00493-007-0041-6[Crossref] 
  2. [2] L. Addario-Berry, K. Dalal and B.A. Reed, Degree constrainted subgraphs, Discrete Appl. Math. 156 (2008) 1168-1174. doi:10.1016/j.dam.2007.05.059[Crossref] Zbl1147.05055
  3. [3] K. Appel and W. Haken, Every planar map is four-colorable, I. Discharging, Illinois J. Math. 21 (1977) 429-490. Zbl0387.05009
  4. [4] M. Bača, S. Jendrol’, K.M. Kathiresan and K. Muthugurupackiam, Entire labeling of plane graph, (submitted). 
  5. [5] M. Bača, S. Jendrol’, M. Miller and J. Ryan, On irregular total labellings, Discrete Math. 307 (2007) 1378-1388. doi:10.1016/j.disc.2005.11.075[Crossref] Zbl1115.05079
  6. [6] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, Heidelberg, 2008). 
  7. [7] A.J. Dong and G.H. Wang, Neighbor sum distinguishing colorings of some graphs, Discrete Math. Algorithms Appl. (2012) 4(4) 1250047. doi:10.1142/S1793830912500474[Crossref] 
  8. [8] E. Flandrin, J.F. Saclé, A. Marczyk, J. Przyby lo and M. Woźniak, Neighbor sum distinguishing index, Graphs Combin. 29 (2013) 1329-1336. doi:10.1007/s00373-012-1191-x[Crossref] Zbl1272.05047
  9. [9] A. Frieze, R.J. Gould, M. Karoński and F. Pfender, On graph irregularity strenght, J. Graph Theory 41 (2002) 120-137. doi:10.1002/jgt.10056[Crossref] Zbl1016.05045
  10. [10] H. Grötzsch, Zur Theorie der discreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel., Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.- Mat. Reihe 8 (1958/1959) 109-120. 
  11. [11] G. Chartrand, M.S. Jacobson, L. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 187-192. 
  12. [12] M. Kalkowski, A note on 1, 2-conjecture, Electron. J. Combin. (to appear). Zbl06582526
  13. [13] M. Kalkowski, M. Karoński and F. Pfender, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Combin. Theory (B) 100 (2010) 347-349. doi:10.1016/j.jctb.2009.06.002[Crossref][WoS] Zbl1209.05087
  14. [14] M. Karo´nski, T. Luczak and A. Thomason, Edge weights and vertex colours, J. Combin. Theory (B) 91 (2004) 151-157. doi:10.1016/j.jctb.2003.12.001[Crossref] Zbl1042.05045
  15. [15] J. Przyby lo and M. Woźniak, On 1, 2 conjecture, Discrete Math. Theor. Comput. Sci. 12 (2010) 101-108. 
  16. [16] T. Wang and Q. Yu, On vertex-coloring 13-edge-weighting, Front. Math. China 3 (2008) 1-7. doi:10.1007/s11464-008-0041-x[WoS][Crossref] Zbl1191.05048
  17. [17] W. Wang and X. Zhu, Entire colouring of plane graphs, J. Combin. Theory (B) 101 (2011) 490-501. doi:10.1016/j.jctb.2011.02.006 [Crossref] Zbl1234.05106

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.