Geodesic
Strong incidence colouring of graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 663-689

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

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},
     publisher = {mathdoc},
     volume = {44},
     number = {2},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/