×

A note on face coloring entire weightings of plane graphs. (English) Zbl 1290.05065

Summary: Given a weighting of all elements of a 2-connected plane graph \(G = (V,E, F)\), let \(f({\alpha})\) denote the sum of the weights of the edges and vertices incident with the face \(\alpha\) and also the weight of \(\alpha\). Such an entire weighting is a proper face colouring provided that \(f({\alpha}) \neq f({\beta})\) for every two faces \({\alpha}\) and \(\beta\) 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.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C22 Signed and weighted graphs
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[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; · Zbl 1127.05034
[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; · Zbl 1147.05055
[3] K. Appel and W. Haken, Every planar map is four-colorable, I. Discharging, Illinois J. Math. 21 (1977) 429-490.; · Zbl 0387.05009
[4] M. Bača, S. Jendrol’, K.M. Kathiresan and K. Muthugurupackiam, Entire labeling of plane graph, (submitted).;
[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; · Zbl 1115.05079
[6] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, Heidelberg, 2008).; · Zbl 1134.05001
[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; · Zbl 1257.05040
[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; · Zbl 1272.05047
[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; · Zbl 1016.05045
[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] G. Chartrand, M.S. Jacobson, L. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 187-192.; · Zbl 0671.05060
[12] M. Kalkowski, A note on 1, 2-conjecture, Electron. J. Combin. (to appear).; · Zbl 1342.90019
[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; · Zbl 1209.05087
[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; · Zbl 1042.05045
[15] J. Przyby lo and M. Woźniak, On 1, 2 conjecture, Discrete Math. Theor. Comput. Sci. 12 (2010) 101-108.; · Zbl 1250.05093
[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; · Zbl 1191.05048
[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; · Zbl 1234.05106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.