A note on insecure 3-Colorings of graph vertices

WOLFRAM MATERIALS for the ARTICLE:

Robert Cowen (2021).

Mixing Numbers and Unfriendly Colorings of Graphs.

The Mathematica Journal, 23.

Mixing Numbers and Unfriendly Colorings of Graphs « The Mathematica Journal

Full article in PDF.

The Mathematica language has a robust set of built-in functions for graph theory explorations. Many of them come from the old Combinatorica package developed by Steven Skiena. However there is not much that deals with graph coloring. Out of necessity, I have created my own functions and have recently published a paper in The Mathematica Journal and I am adding a notebook with additional material here. Hopefully this will be useful to researchers in graph theory and encourage others to develop additional useful material for those interested in graph theory coloring problems.

Insecure 3-Coloring5.nb (222 KB)

6 Likes

news-congrads-kkluyshnik-02-04-19.jpg – you have earned Featured Contributor Badge 2015-11-02_10-07-11.png
Your exceptional post has been selected for our editorial columns Staff Picks http://wolfr.am/StaffPicks and Publication Materials https://wolfr.am/PubMat and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

Thanks for this honor! I should also like to thank George Beck who was the editor for my Mathematica Journal articles and who has taught me much about the Mathematica programming language.

3 Likes

If you work with graphs and colourings in Mathematica, you may find the IGraph/M package interesting. It has had very competitive graph colouring functionality for many years now, and also provides most graph-related functionality from the old Combinatorica, but in a much more performant way.

Needs["IGraphM`"]

PetersenGraph[VertexSize -> Large, EdgeStyle -> Thickness[0.05]] // 
  IGVertexMap[ColorData[97], VertexStyle -> IGMinimumVertexColoring] //
  IGEdgeMap[ColorData[99], EdgeStyle -> IGMinimumEdgeColoring]

1 Like