Geodesic
Facial [r,s,t]-Colorings of Plane Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 629-645.

Voir la notice de l'article provenant de la source Library of Science

Let G be a plane graph. Two edges are facially adjacent in G if they are consecutive edges on the boundary walk of a face of G. Given nonnegative integers r, s, and t, a facial [r, s, t]-coloring of a plane graph G = (V,E) is a mapping f : V ∪ E →1, . . ., k such that |f(v_1) − f(v_2)| ≥ r for every two adjacent vertices v_1 and v_2, | f(e_1) − f(e_2)| ≥ s for every two facially adjacent edges e_1 and e_2, and | f(v) − f(e)| ≥ t for all pairs of incident vertices v and edges e. The facial [r, s, t]-chromatic number χ_r,s,t (G) of G is defined to be the minimum k such that G admits a facial [r, s, t]-coloring with colors 1, . . ., k. In this paper we show that χ_r,s,t (G) ≤ 3r + 3s + t + 1 for every plane graph G. For some triplets [r, s, t] and for some families of plane graphs this bound is improved. Special attention is devoted to the cases when the parameters r, s, and t are small.
Keywords: plane graph, boundary walk, edge-coloring, vertex-coloring, total-coloring 
@article{DMGT_2019_39_3_a1,
     author = {Czap, J\'ulius and \v{S}ugerek, Peter and Jendrol{\textquoteright}, Stanislav and Valiska, Juraj},
     title = {Facial {[r,s,t]-Colorings} of {Plane} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {629--645},
     publisher = {mathdoc},
     volume = {39},
     number = {3},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a1/}
}
TY  - JOUR
AU  - Czap, Július
AU  - Šugerek, Peter
AU  - Jendrol’, Stanislav
AU  - Valiska, Juraj
TI  - Facial [r,s,t]-Colorings of Plane Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 629
EP  - 645
VL  - 39
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a1/
LA  - en
ID  - DMGT_2019_39_3_a1
ER  - 
%0 Journal Article
%A Czap, Július
%A Šugerek, Peter
%A Jendrol’, Stanislav
%A Valiska, Juraj
%T Facial [r,s,t]-Colorings of Plane Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 629-645
%V 39
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a1/
%G en
%F DMGT_2019_39_3_a1
Czap, Július; Šugerek, Peter; Jendrol’, Stanislav; Valiska, Juraj. Facial [r,s,t]-Colorings of Plane Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 629-645. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a1/

[1] K. Appel and W. Haken, Every planar map is four colorable, Part I: Discharging, Illinois J. Math. 21 (1977) 429–490.

[2] K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Part II: Reducibility, Illinois J. Math. 21 (1977) 491–567.

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).

[4] D. Chen and W. Wang, (2, 1) -total labelling of outerplanar graphs, Discrete Appl. Math. 155 (2007) 2585–2593. doi:10.1016/j.dam.2007.07.016

[5] J. Czap and S. Jendrol’, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703. doi:10.1016/j.disc.2016.07.026

[6] J. Czap and P. Šugerek, Facial total-coloring of bipartite plane graphs, Int. J. Pure Appl. Math. 115 (2017) 115–121. doi:10.12732/ijpam.v115i1.9

[7] L. Dekar, B. Effantin and H. Kheddouci, [ r, s, t ] -colorings of graph products, Graphs Combin. 30 (2014) 1135–1147. doi:10.1007/s00373-013-1338-4

[8] L. Dekar, B. Effantin and H. Kheddouci, [ r, s, t ] -colorings of trees and bipartite graphs, Discrete Math. 310 (2010) 260–269. doi:10.1016/j.disc.2008.09.021

[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

[10] I. Fabrici, S. Jendrol’ and M. Vrbjarová, Facial entire colourings of plane graphs, Discrete Math. 339 (2016) 626–631. doi:10.1016/j.disc.2015.09.011

[11] I. Fabrici, S. Jendrol’ and M. Voigt, Facial list colourings of plane graphs, Discrete Math. 339 (2016) 2826–2831. doi:10.1016/j.disc.2016.05.034

[12] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Universit¨at, Halle-Wittenberg, Math.-Nat. Reihe 8 (1959) 109–120.

[13] T. Hasunuma, T. Ishii, H. Ono and Y. Uno, A tight upper bound on the (2, 1) -total labeling number of outerplanar graphs, J. Discrete Algorithms 14 (2012) 189–206. doi:10.1016/j.jda.2011.12.020

[14] F. Havet and S. Thomassé, Complexity of ( p, 1) -total labelling, Discrete Appl. Math. 157 (2009) 2859–2870. doi:10.1016/j.dam.2009.03.021

[15] F. Havet and M.-L. Yu, ( p, 1) -total labelling of graphs, Discrete Math. 308 (2008) 496–513. doi:10.1016/j.disc.2007.03.034

[16] A. Kemnitz and J. Lehmann, [ r, s, t ] -colorings of stars, Congr. Numer. 185 (2007) 65–80.

[17] A. Kemnitz, J. Lehmann and M. Marangio, [1, 1, 2] -colorings of complete graphs, Congr. Numer. 208 (2011) 99–113.

[18] A. Kemnitz and M. Marangio, [ r, s, t ] -colorings of graphs, Discrete Math. 307 (2007) 199–207. doi:10.1016/j.disc.2006.06.030

[19] A. Kemnitz, M. Marangio and P. Mihók, [ r, s, t ] -chromatic numbers and hereditary properties of graphs, Discrete Math. 307 (2007) 916–922. doi:10.1016/j.disc.2005.11.055

[20] A. Kemnitz, M. Marangio and Zs. Tuza, [1, 1, t ] -colorings of complete graphs, Graphs Combin. 29 (2013) 1041–1050. doi:10.1007/s00373-012-1153-3

[21] W. Liao and M. Li, [ r, s, t ] -colorings of friendship graphs and wheels, Graphs Combin. 31 (2015) 2275–2292. doi:10.1007/s00373-014-1502-5

[22] I. Schiermeyer and M.S. Villà, [ r, s, t ] -colourings of paths, Opuscula Math. 27 (2007) 131–149.

[23] G. Sethuraman and A. Velankanni, (2, 1) -total labeling of a class of subcubic graphs, Electron. Notes Discrete Math. 48 (2015) 259–266. doi:10.1016/j.endm.2015.05.039

[24] P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh 10 (1880) 729.

[25] M.S. Villà, [ r, s, t ]-Colourings of Paths, Cycles and Stars, Doctoral Thesis (TU Bergakademie, Freiberg, 2005).

[26] W. Wang and D. Chen, (2, 1) -total number of trees with maximum degree three, Inform. Process. Lett. 109 (2009) 805–810. doi:10.1016/j.ipl.2009.03.027