GraphTheory - Maple Programming Help

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

GraphTheory

 Mycielski

 Calling Sequence Mycielski(G)

Parameters

 G - undirected graph

Description

 • Mycielski is a graph construction which, given a graph G on $n$ vertices, returns a graph on $2n+1$ vertices. If G is triangle-free with chromatic number $k$, then the returned graph is triangle-free with chromatic number $k+1$.

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)
 > $G≔\mathrm{Mycielski}\left(P\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 21 vertices and 55 edge\left(s\right)}}$ (2)
 > $\mathrm{ChromaticNumber}\left(G,'\mathrm{bound}'\right)$
 ${3}{..}{4}$ (3)
 > $\mathrm{ChromaticNumber}\left(G\right)$
 ${4}$ (4)