A Note On Vertex Colorings Of Plane Graphs

Igor Fabricia; Stanislav Jendrol’; Roman Soták

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 4, page 849-855
  • ISSN: 2083-5892

Abstract

top
Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.

How to cite

top

Igor Fabricia, Stanislav Jendrol’, and Roman Soták. "A Note On Vertex Colorings Of Plane Graphs." Discussiones Mathematicae Graph Theory 34.4 (2014): 849-855. <http://eudml.org/doc/269816>.

@article{IgorFabricia2014,
abstract = {Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in \{1, 2, 3\}. In a special case, the value 3 is improved to 2.},
author = {Igor Fabricia, Stanislav Jendrol’, Roman Soták},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {plane graph; vertex coloring.; vertex coloring},
language = {eng},
number = {4},
pages = {849-855},
title = {A Note On Vertex Colorings Of Plane Graphs},
url = {http://eudml.org/doc/269816},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Igor Fabricia
AU - Stanislav Jendrol’
AU - Roman Soták
TI - A Note On Vertex Colorings Of Plane Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 4
SP - 849
EP - 855
AB - Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.
LA - eng
KW - plane graph; vertex coloring.; vertex coloring
UR - http://eudml.org/doc/269816
ER -

References

top
  1. [1] L. Addario-Berry, K. Dalal, C. McDiarmid, B.A. Reed and A. Thomason, Vertexcoloring edge-weigtings, Combinatorica 27 (2007) 1-12. doi:10.1007/s00493-007-0041-6 
  2. [2] L. Addario-Berry, K. Dalaland and B.A. Reed, Degree constrainted subgraphs, Discrete Appl. Math. 156 (2008) 1168-1174. doi:10.1016/j.dam.2007.05.059 
  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. Axenovich, J. Harant, J. Przyby lo, R. Soták and M. Voigt, A note on adjacent vertex distinguishing colorings number of graphs, Electron. J. Combin. (submitted). Zbl1333.05101
  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 Zbl1115.05079
  6. [6] T. Bartnicki, B. Bosek, S. Czerwiński, J. Grytczuk, G. Matecki and W. Żelazny, Additive colorings of planar graphs, Graphs Combin. 30 (2014) 1087-1098. doi:10.1007/s00373-013-1331-y Zbl1298.05102
  7. [7] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). 
  8. [8] G. Chartrand, M.S. Jacobson, L. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 187-192. 
  9. [9] S. Czerwi´nski, J. Grytczuk and W. ˙ Zelazny, Lucky labelings of graphs, Inform. Process. Lett. 109 (2009) 1078-1081. doi:10.1016/j.ipl.2009.05.011 Zbl1197.05125
  10. [10] R. Diestel, Graph Theory (Springer, 2000). 
  11. [11] A. Frieze, R.J. Gould, M. Karónski and F. Pfender, On graph irregularity strenght , J. Graph Theory 41 (2002) 120-137. doi:10.1002/jgt.10056 Zbl1016.05045
  12. [12] S. Jendrol’ and P. Šugerek, A note on face coloring entire weightings of plane graphs, Discuss. Math. Graph Theory 34 (2014) 421-426. doi:10.7151/dmgt.1738 Zbl1290.05065
  13. [13] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley, 1995). 
  14. [14] M. Kalkowski, A note on 1, 2-conjecture, Electron. J. Combin. (to appear). Zbl06582526
  15. [15] M. Kalkowski, M. Karónski 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 Zbl1209.05087
  16. [16] M. Karo´nski and T. Luczak, A. Thomason, Edge weights and vertex colors, J. Combin. Theory (B) 91 (2004) 151-157. doi:10.1016/j.jctb.2003.12.001 
  17. [17] J. Przyby lo and M. Wózniak, On 1, 2 conjecture, Discrete Math. Theor. Comput. Sci. 12 (2010) 101-108. 
  18. [18] T. Wang and Q. Yu, On vertex-coloring 13-edge-weighting, Front. Math. China 3 (2008) 1-7. doi:10.1007/s11461-008-0009-8 Zbl1191.05048
  19. [19] W. Wang and X. Zhu, Entire coloring of plane graphs, J. Combin. Theory (B) 101 (2011) 490-501. doi:10.1016/j.jctb.2011.02.006 

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.