pith. sign in

arxiv: 1505.04908 · v3 · pith:RVGIAZLXnew · submitted 2015-05-19 · 🧮 math.CO

On incidence coloring conjecture in Cartesian products of graphs

classification 🧮 math.CO
keywords coloringincidencecolorsgraphgraphsincidencesadjacentcartesian
0
0 comments X
read the original abstract

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: $(a)$ $v = u$, $(b)$ $e = f$, or $(c)$ $vu \in \{e,f\}$. An incidence coloring of $G$ is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most $\Delta(G) + 2$ colors are needed for an incidence coloring of any graph $G$. The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph $G$ for which $G$ admits an incidence coloring with at most $\Delta(G) + 2$ colors.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.