In graph theory, a mixed graph G = (V, E, A) is a graph consisting of a set of vertices V, a set of (undirected) edges E, and a set of directed edges (or arcs) A.

Consider adjacent vertices ${\displaystyle u,v\in V}$. A directed edge, called an arc, is an edge with an orientation and can be denoted as ${\displaystyle {\overrightarrow {uv}}}$ or ${\displaystyle (u,v)}$ (note that ${\displaystyle u}$ is the tail and ${\displaystyle v}$ is the head of the arc). Also, an undirected edge, or edge, is an edge with no orientation and can be denoted as ${\displaystyle uv}$ or ${\displaystyle [u,v]}$.

For the purpose of our example we will not be considering loops or multiple edges of mixed graphs.

A walk in a mixed graph is a sequence ${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k}}$ of vertices and edges/arcs such that for every index ${\displaystyle i}$, either ${\displaystyle c_{i}=v_{i}v_{i+1}}$ is an edge of the graph or ${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1}}}}$ is an arc of the graph. This walk is a path if it does not repeat any edges, arcs, or vertices, except possibly the first and last vertices. A walk is closed if its first and last vertices are the same, and a closed path is a cycle. A mixed graph is acyclic if it does not contain a cycle.

Mixed graph coloring can be thought of as labeling or an assignment of k different colors (where k is a positive integer) to the vertices of a mixed graph. Different colors must be assigned to vertices that are connected by an edge. The colors may be represented by the numbers from 1 to k, and for a directed arc, the tail of the arc must be colored by a smaller number than the head of the arc.

For example, consider the figure to the right. Our available k-colors to color our mixed graph are {1, 2, 3}. Since u and v are connected by an edge, they must receive different colors or labelings (u and v are labelled 1 and 2, respectively). We also have an arc from v to w. Since orientation assigns an ordering, we must label the tail (v) with a smaller color (or integer from our set) than the head (w) of our arc.

A (strong) proper k-coloring of a mixed graph is a function c : V → [k] where [k] := {1, 2, …, k} such that c(u) ≠ c(v) if uv ∈ E and c(u) < c(v) if ${\displaystyle {\overrightarrow {uv}}\in A}$.

A weaker condition on our arcs can be applied and we can consider a weak proper k-coloring of a mixed graph to be a function c : V → [k] where [k] := {1, 2, …, k} such that c(u) ≠ c(v) if uv ∈ E and c(u) ≤ c(v) if ${\displaystyle {\overrightarrow {uv}}\in A}$. Referring back to our example, this means that we can label both the head and tail of (v,w) with the positive integer 2.