Source author record

Samia Kerdjoudj

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Injective edge-coloring of sparse graphs

An injective edge-coloring $c$ of a graph $G$ is an edge-coloring such that if $e_1$ , $e_2$ , and $e_3$ are three consecutive edges in $G$ (they are consecutive if they form a path or a cycle of length three), then $e_1$ and $e_3$ receive different colors. The minimum integer $k$ such that, $G$ has an injective edge-coloring with $k$ colors, is called the injective chromatic index of $G$ ( $χ'_{\textrm{inj}}(G)$ ). This parameter was introduced by Cardoso et \textit{al.} \cite{CCCD} motivated by the Packet Radio Network problem. They proved that computing $χ'_{\textrm{inj}}(G)$ of a graph $G$ is NP-hard. We give new upper bounds for this parameter and we present the relationships of the injective edge-coloring with other colorings of graphs. The obtained general bound gives 8 for the injective chromatic index of a subcubic graph. If the graph is subcubic bipartite we improve this last bound. We prove that a subcubic bipartite graph has an injective chromatic index bounded by $6$ . We also prove that if $G$ is a subcubic graph with maximum average degree less than $\frac{7}{3}$ (resp. $\frac{8}{3}$ , $3$ ), then $G$ admits an injective edge-coloring with at most 4 (resp. $6$ , $7$ ) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs.

preprint2015arXiv

Incidence coloring of graphs with high maximum average degree

An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$ . Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$ , (ii) $e = f$ or (iii) $vw = e$ or $f$ . An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In 2005, Hosseini Dolama \emph{et al.}~\citep{ds05} proved that every graph with maximum average degree strictly less than $3$ can be incidence colored with $Δ+3$ colors. Recently, Bonamy \emph{et al.}~\citep{Bonamy} proved that every graph with maximum degree at least $4$ and with maximum average degree strictly less than $\frac{7}{3}$ admits an incidence $(Δ+1)$ -coloring. In this paper we give bounds for the number of colors needed to color graphs having maximum average degrees bounded by different values between $4$ and $6$ . In particular we prove that every graph with maximum degree at least $7$ and with maximum average degree less than $4$ admits an incidence $(Δ+3)$ -coloring. This result implies that every triangle-free planar graph with maximum degree at least $7$ is incidence $(Δ+3)$ -colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence $(Δ+ 7)$ -coloring. More generally, we prove that $Δ+k-1$ colors are enough when the maximum average degree is less than $k$ and the maximum degree is sufficiently large.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.