In
graph theory, path coloring usually refers to one of two problems:
* The problem of coloring a
(multi)set of
paths in graph
, in such a way that any two paths of
which share an edge in
receive different colors. Set
and graph
are provided at input. This formulation is equivalent to
vertex coloring the ''conflict graph'' of set
, i.e. a graph with vertex set
and edges connecting all pairs of paths of
which are not edge-disjoint with respect to
.
* The problem of coloring (in accordance with the above definition) any chosen
(multi)set of paths in
, such that the set of pairs of end-vertices of paths from
is equal to some set or multiset
, called a ''set of requests''. Set
and graph
are provided at input. This problem is a special case of a more general class of graph routing problems, known as
call scheduling.
In both the above problems, the goal is usually to minimise the number of colors used in the coloring. In different variants of path coloring,
may be a
simple graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
,
digraph or
multigraph.
References
''The Complexity of Path Coloring and Call Scheduling''by Thomas Erlebach and Klaus Jansen
by Viggo Kann (problem: Minimum Path Coloring)
Graph coloring
{{Combin-stub