ﻻ يوجد ملخص باللغة العربية
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 $Delta+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 $(Delta+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 $(Delta+3)$-coloring. This result implies that every triangle-free planar graph with maximum degree at least $7$ is incidence $(Delta+3)$-colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence $(Delta + 7)$-coloring. More generally, we prove that $Delta+k-1$ colors are enough when the maximum average degree is less than $k$ and the maximum degree is sufficiently large.
For a graph $G$ and integer $qgeq 2$, an edge $q$-coloring of $G$ is an assignment of colors to edges of $G$, such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$-coloring problem seeks to maximize the number of
If the vertices of a graph $G$ are colored with $k$ colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then $G$ is said to be equitably $k$-colorable. Let $|G|$ denote the number
A strong edge-coloring of a graph $G$ is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by $chi_{s}(G)$ which is the minimum number of colors that allow a strong edge-c
We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic number of a digraph, and the arboricity of a graph.) For any girth and suff
A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and vs neighbors. Such colorings have applications in wirel