Predavatelj: Borut Lužar
An incidence in a graph $G$ is a pair $(v,e)$ where $v$
is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$. Two incidences $(v,e)$ and $(u,f)$ are adjacent if at least one of the
following holds: (1) $v = u$, (2) $e = f$, or (3) $vuin{e,f}$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. The originators conjectured
that every graph G admits an incidence coloring with at most Δ(G)+2 colors. The conjecture is false in general, but there are
many classes of graphs for which it holds. We will present the main
results from the field and introduce some of our recent ones. Namely,
we will focus on incidence coloring of Cartesian products of graphs
and subquartic graphs.
is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$. Two incidences $(v,e)$ and $(u,f)$ are adjacent if at least one of the
following holds: (1) $v = u$, (2) $e = f$, or (3) $vuin{e,f}$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. The originators conjectured
that every graph G admits an incidence coloring with at most Δ(G)+2 colors. The conjecture is false in general, but there are
many classes of graphs for which it holds. We will present the main
results from the field and introduce some of our recent ones. Namely,
we will focus on incidence coloring of Cartesian products of graphs
and subquartic graphs.
