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
Access Full Article
topAbstract
topHow to cite
topIgor 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] 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] 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] K. Appel and W. Haken, Every planar map is four-colorable, I. Discharging, Illinois J. Math. 21 (1977) 429-490. Zbl0387.05009
- [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] 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] 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] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
- [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] 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] R. Diestel, Graph Theory (Springer, 2000).
- [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] 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] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley, 1995).
- [14] M. Kalkowski, A note on 1, 2-conjecture, Electron. J. Combin. (to appear). Zbl06582526
- [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] 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] J. Przyby lo and M. Wózniak, On 1, 2 conjecture, Discrete Math. Theor. Comput. Sci. 12 (2010) 101-108.
- [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] 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 ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.