GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/CircularChromaticIndex

GraphTheory

 CircularChromaticIndex
 CircularEdgeChromaticNumber

 Calling Sequence CircularChromaticIndex(G, col) CircularEdgeChromaticNumber(G, col)

Parameters

 G - undirected unweighted graph col - (optional) name used to return the list of colors of an optimal proper coloring

Description

 • The CircularChromaticIndex and CircularEdgeChromaticNumber commands return the circular chromatic index (circular edge chromatic number) of a graph G. If a name col is specified, then this name is assigned the list of colors of an optimal proper edge coloring. The algorithm uses a backtracking technique.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{:=}{\mathrm{Graph 1: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{CircularChromaticIndex}\left(P,'\mathrm{col}'\right)$
 $\frac{{11}}{{3}}$ (2)
 > $\mathrm{col}$
 $\left[\left\{{1}{,}{2}\right\}{=}{0}{,}\left\{{1}{,}{5}\right\}{=}{3}{,}\left\{{1}{,}{6}\right\}{=}{6}{,}\left\{{2}{,}{3}\right\}{=}{3}{,}\left\{{2}{,}{9}\right\}{=}{8}{,}\left\{{3}{,}{4}\right\}{=}{6}{,}\left\{{3}{,}{7}\right\}{=}{9}{,}\left\{{4}{,}{5}\right\}{=}{10}{,}\left\{{4}{,}{10}\right\}{=}{2}{,}\left\{{5}{,}{8}\right\}{=}{7}{,}\left\{{6}{,}{7}\right\}{=}{1}{,}\left\{{6}{,}{10}\right\}{=}{9}{,}\left\{{7}{,}{8}\right\}{=}{4}{,}\left\{{8}{,}{9}\right\}{=}{0}{,}\left\{{9}{,}{10}\right\}{=}{5}\right]$ (3)