A script to compute the chromatic number of graphs in Graphviz DOT format.

chromatic.sh

#!/bin/bash

file_gv=$1

n_edges_re='s/\([0-9]*\) %.*/\1/p'

n_edges=`gc -e $file_gv\
         | sed -n "${n_edges_re}"\
         | tr -d ' '`

if [[ ${n_edges} -eq 0 ]] ; then
    echo 1
    exit 1
fi

max_degree_re='s/max degree = \([0-9]*\).*/\1/p'

max_degree=`gvpr -f maxdeg $file_gv\
            | sed -n "${max_degree_re}"`

graph_data=`cat $file_gv\
            | sed -n 's/\([0-9]*\) -- \([0-9]*\);/\1--\2,/p'\
            | tr -d ' \t\n\r\f'\
            | sed '$s/.$//'`

cp=`echo $graph_data\
    | tutte --chromatic --stdin\
    | sed -n 's/^CP\[1\] :=\(.*\) :/\1/p'`

s="
D: ${max_degree}$
cp: ${cp}$
chi: for i: 1 thru D + 1 do
       if at(cp, x = i) > 0 then return (i)$
print(chi);"

maxima --very-quiet --batch-string="$s"\
  | tail -n 1\
  | tr -d ' \t\r\f'