Geodesic
Strong incidence colouring of graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 663-689 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

An incidence of a graph G is a pair (v,e) where v is a vertex of G and e is an edge of G incident with v. Two incidences (v,e) and (w,f) of G are adjacent whenever (i) v=w, or (ii) e=f, or (iii) vw=e or f. An incidence p-colouring of G is a mapping from the set of incidences of G to the set of colours {1, . . . , p} such that every two adjacent incidences receive distinct colours. Incidence colouring has been introduced by Brualdi and Quinn Massey in 1993 and, since then, studied by several authors. In this paper, we introduce and study the strong version of incidence colouring, where incidences adjacent to the same incidence must also get distinct colours. We determine the exact value of — or upper bounds on — the strong incidence chromatic number of several classes of graphs, namely cycles, wheel graphs, trees, ladder graphs, square grids and subclasses of Halin graphs.
Keywords: strong incidence colouring, incidence colouring, tree, Halin graph, ladder graph, square grids, necklace, double star, wheel graph 
@article{DMGT_2024_44_2_a12,
     author = {Benmedjdoub, Brahim and Sopena, \'Eric},
     title = {Strong incidence colouring of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {663--689},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a12/}
}
TY  - JOUR
AU  - Benmedjdoub, Brahim
AU  - Sopena, Éric
TI  - Strong incidence colouring of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 663
EP  - 689
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a12/
LA  - en
ID  - DMGT_2024_44_2_a12
ER  - 
%0 Journal Article
%A Benmedjdoub, Brahim
%A Sopena, Éric
%T Strong incidence colouring of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 663-689
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a12/
%G en
%F DMGT_2024_44_2_a12
Benmedjdoub, Brahim; Sopena, Éric. Strong incidence colouring of graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 663-689. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a12/

[1] B. Benmedjdoub, I. Bouchemakh and É. Sopena, Incidence choosability of graphs, Discrete Appl. Math. 265 (2019) 40–55. https://doi.org/10.1016/j.dam.2019.04.027

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

[3] P. Gregor, B. Lužar and R. Soták, Note on incidence chromatic number of subquartic graphs, J. Comb. Optim. 34 (2017) 174–181. https://doi.org/10.1007/s10878-016-0072-2

[4] P. Gregor, B. Lužar and R. Soták, On incidence coloring conjecture in Cartesian products of graphs, Discrete Appl. Math. 213 (2016) 93–100. https://doi.org/10.1016/j.dam.2016.04.030

[5] R. Halin, Studies on minimally n-connected graphs, in: Proc. Combinatorial Mathematics and its Aplications, Oxford 1969 (Academic Press, London, 1971) 129–136.

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

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

[8] A. Prowse and D.R. Woodall, Choosability of powers of circuits, Graphs Combin. 19 (2003) 137–144. https://doi.org/10.1007/s00373-002-0486-8

[9] W.C. Shiu, P.C.B. Lam and W.K. Tam, On strong chromatic index of Halin graph, J. Combin. Math. Combin. Comput. 57 (2006) 211–222.

[10] É. Sopena and J. Wu, The incidence chromatic number of toroidal grids, Discuss. Math. Graph Theory 33 (2013) 315–327. https://doi.org/10.7151/dmgt.1663

[11] S.-D. Wang, D.-L. Chen and S.-C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397–405. https://doi.org/10.1016/S0012-365X(01)00302-8

[12] J. Wu, Some results on the incidence coloring number of graphs, Discrete Math. 309 (2009) 3866–3870. https://doi.org/10.1016/j.disc.2008.10.027