Code covered by the BSD License  

Highlights from
Matgraph

Matgraph

by

 

14 Mar 2008 (Updated )

Toolbox for working with simple, undirected graphs

Coloring graphs in Matgraph

Coloring graphs in Matgraph

We illustrate how to find colorings of graphs and display the results.

Contents

Use the Buckyball graph

We set g to be the Bucky graph.

g = graph;
bucky(g)

Greedy coloring

First we find a greedy coloring of the graph and display the results. Notice that this coloring uses four colors.

c = color(g); % uses algorithm 'greedy' by default
disp(['This coloring uses ', int2str(np(c)),' colors']);
cdraw(g,c);
This coloring uses 4 colors

Optimal coloring

An optimal coloring is slower (and may be intolerable on large graphs). However, for the Bucky graph, it uses fewer colors than the greedy algorithm.

tic; c = color(g,'optimal'); toc
disp(['This coloring uses ', int2str(np(c)),' colors']);
cdraw(g,c);
Elapsed time is 0.598491 seconds.
This coloring uses 3 colors

Release the graph

free(g);

Contact us