Mixed graph

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.

[2] 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

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.

[3] Different colors must be assigned to vertices that are connected by an edge.

Our available k-colors to color our mixed graph are {1, 2, 3}.

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

[1] 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

[1] Referring back to our example, this means that we can label both the head and tail of (v,w) with the positive integer 2.

A coloring may or may not exist for a mixed graph.

[2] If such a k-coloring exists, then we refer to the smallest k needed in order to properly color our graph as the chromatic number, denoted by χ(G).

[2] The number of proper k-colorings is a polynomial function of k called the chromatic polynomial of our graph G (by analogy with the chromatic polynomial of undirected graphs) and can be denoted by χG(k).

[1] The deletion–contraction method can be used to compute weak chromatic polynomials of mixed graphs.

This method involves deleting (i.e., removing) an edge or arc and possibly joining the remaining vertices incident to that edge or arc to form one vertex.

From Propositions given in Beck et al.[4] we obtain the following equations to compute the chromatic polynomial of a mixed graph:[5] Mixed graphs may be used to model job shop scheduling problems in which a collection of tasks is to be performed, subject to certain timing constraints.

In this sort of problem, undirected edges may be used to model a constraint that two tasks are incompatible (they cannot be performed simultaneously).

Directed edges may be used to model precedence constraints, in which one task must be performed before another.

The mixed graph coloring problem can be used to find a schedule of minimum length for performing all the tasks.

[2] Mixed graphs are also used as graphical models for Bayesian inference.

In this context, an acyclic mixed graph (one with no cycles of directed edges) is also called a chain graph.

Undirected edges, instead, indicate a non-causal correlation between two events.