On arc-coloring of subcubic graphs

Alexandre Pinlou

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

A homomorphism from an oriented graph $G$ to an oriented graph $H$ is a mapping $\varphi$ from the set of vertices of $G$ to the set of vertices of $H$ such that $\overrightarrow{\varphi(u)\varphi(v)}$ is an arc in $H$ whenever $\overrightarrow{uv}$ is an arc in $G$. The oriented chromatic index of an oriented graph $G$ is the minimum number of vertices in an oriented graph $H$ such that there exists a homomorphism from the line digraph $LD(G)$ of $G$ to $H$ (Recall that $LD(G)$ is given by $V(LD(G))=A(G)$ and $ \overrightarrow{ab}\in A(LD(G))$ whenever $a=\overrightarrow{uv}$ and $b=\overrightarrow{vw}$). We prove that every oriented subcubic graph has oriented chromatic index at most $7$ and construct a subcubic graph with oriented chromatic index $6$.

Détail

DOI : 10.37236/1095

Classification : 05C15
Mots-clés : chromatic index, oriented graph