Geodesic
Facial Incidence Colorings of Embedded Multigraphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 81-93.

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

Let G be a cellular embedding of a multigraph in a 2-manifold. Two distinct edges e1, e2 ∈ E(G) are facially adjacent if they are consecutive on a facial walk of a face f ∈ F(G). An incidence of the multigraph G is a pair (v, e), where v ∈ V (G), e ∈ E(G) and v is incident with e in G. Two distinct incidences (v1, e1) and (v2, e2) of G are facially adjacent if either e1 = e2 or e1, e2 are facially adjacent and either v1 = v2 or v1 ≠ v2 and there is i ∈ 1, 2 such that ei is incident with both v1, v2. A facial incidence coloring of G assigns a color to each incidence of G in such a way that facially adjacent incidences get distinct colors. In this note we show that any embedded multigraph has a facial incidence coloring with seven colors. This bound is improved to six for several wide families of plane graphs and to four for plane triangulations.
Keywords: embedded multigraph, incidence, facial incidence coloring 
@article{DMGT_2019_39_1_a7,
     author = {Jendrol{\textquoteright}, Stanislav and Hor\v{n}\'ak, Mirko and Sot\'ak, Roman},
     title = {Facial {Incidence} {Colorings} of {Embedded} {Multigraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {81--93},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a7/}
}
TY  - JOUR
AU  - Jendrol’, Stanislav
AU  - Horňák, Mirko
AU  - Soták, Roman
TI  - Facial Incidence Colorings of Embedded Multigraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 81
EP  - 93
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a7/
LA  - en
ID  - DMGT_2019_39_1_a7
ER  - 
%0 Journal Article
%A Jendrol’, Stanislav
%A Horňák, Mirko
%A Soták, Roman
%T Facial Incidence Colorings of Embedded Multigraphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 81-93
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a7/
%G en
%F DMGT_2019_39_1_a7
Jendrol’, Stanislav; Horňák, Mirko; Soták, Roman. Facial Incidence Colorings of Embedded Multigraphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 81-93. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a7/

[1] I. Algor and N. Alon, The star arboricity of graphs, Discrete Math. 75 (1989) 11-22. doi: 10.1016/0012-365X(89)90073-3

[2] K. Appel and W. Haken, Every Planar Map is Four Colorable (Contemporary Mathematics Vol. 98, American Mathematical Society, Providence, Rhode Island, 1989).

[3] M. Axenovich, T. Ueckerdt and P. Weiner, Splitting planar graphs of girth 6 into two linear forests with short paths, J. Graph Theory 85 (2017) 601-618. doi: 10.1002/jgt.22093

[4] M. Bonamy, B. Lévêque and A. Pinlou, 2-distance coloring of sparse graphs, J. Graph Theory 77 (2014) 190-218. doi: 10.1002/jgt.21782

[5] R.A. Brualdi and J.J. Quinn Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58. doi: 10.1016/0012-365X(93)90286-3

[6] 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

[7] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94. doi: 10.1016/0012-365X(91)90166-Y

[8] B. Guiduli, On incidence coloring and star arboricity of graphs, Discrete Math. 163 (1997) 275-278. doi: 10.1016/0012-365X(95)00342-T

[9] P. Hall, On representatives of subsets, J. Lond. Math. Soc. 10 (1935) 26-30. doi: 10.1112/jlms/s1-10.37.26

[10] M. Hosseini Dolama, É. Sopena and X. Zhu, Incidence coloring of k-degenerated graphs, Discrete Math. 283 (2004) 121-128. doi: 10.1016/j.disc.2004.01.015

[11] M. Hosseini Dolama and É. Sopena, On the maximum average degree and the inci- dence chromatic number of a graph, Discrete Math. Theor. Comput. Sci. 7 (2005) 203-216.

[12] X. Li and J. Tu, NP-completeness of 4-incidence colorability of semicubic graphs, Discrete Math. 308 (2008) 1334-1340. doi: 10.1016/j.disc.2007.03.076

[13] M. Maydanskyi, The incidence coloring conjecture for graphs of maximum degree 3, Discrete Math. 292 (2005) 131-141. doi: 10.1016/j.disc.2005.02.003

[14] K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73-75. doi: 10.1002/jgt.3190140108

[15] N. Robertson, D. Sanders, P. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997) 2-44. doi: 10.1006/jctb.1997.1750

[16] W.C. Shiu, P.C.B. Lam and D.L. Chen, On incidence coloring for some cubic graphs, Discrete Math. 252 (2002) 259-266. doi: 10.1016/S0012-365X(01)00457-5

[17] W.C. Shiu and P.K. Sun, Invalid proofs on incidence coloring, Discrete Math. 308 (2008) 6575-6580. doi: 10.1016/j.disc.2007.11.030

[18] P.K. Sun, Incidence coloring of regular graphs and complement graphs, Taiwanese J. Math. 16 (2012) 2289-2295. doi: 10.11650/twjm/1500406852

[19] W.F. Wang and K.W. Lih, Labeling planar graphs with conditions on girth and distance two, SIAM J. Discrete Math. 17 (2003) 264-275. doi: 10.1137/S0895480101390448

[20] J. Wu, Some results on the incidence coloring number of a graph, Discrete Math. 309 (2009) 3866-3870. doi: 10.1016/j.disc.2008.10.027

[21] D. Yang, Fractional incidence coloring and star arboricity of graphs, Ars Combin. 105 (2012) 213-224.