×

On arc-coloring of subcubic graphs. (English) Zbl 1096.05023

Summary: 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\).

MSC:

05C15 Coloring of graphs and hypergraphs