Article in volume
Authors:
Brahim Benmedjdoub
Faculty of Mathematics, Laboratory L'IFORCE, University of Sciences and Technology
Houari Boumediene (USTHB)
email: brahimro@hotmail.com
Éric Sopena
Université de Bordeaux, LaBRI UMR 5800, 351, cours de la Libération, F-33405 Talence Cedex
email: eric.sopena@labri.fr
Title:
Strong incidence colouring of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 663-689
Received: 2021-09-30 , Revised: 2022-07-04 , Accepted: 2022-07-07 , Available online: 2022-08-03 , https://doi.org/10.7151/dmgt.2466
Abstract:
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,\dots,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
References:
- 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 - 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 - 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 - 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 - R. Halin, Studies on minimally $n$-connected graphs, in: Proc. Combinatorial Mathematics and its Aplications, Oxford 1969 (Academic Press, London, 1971) 129–136.
- 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 - 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 - 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 - 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.
- É. 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 - 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 - 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
Close