Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Zeons, Orthozeons, and Graph Colorings

G. Stacey Staples
Tiffany Stellhorn
Journal / Anthology

Advances in Applied Clifford Algebras
Year: 2017
Volume: 27
Page range: 1825-1845

Nilpotent adjacency matrix methods have proven useful for counting self-avoiding walks (paths, trails, cycles, and circuits) in finite graphs. In the current work, these methods are extended for the first time to problems related to graph colorings. Nilpotent-algebraic formulations of graph coloring problems include necessary and sufficient conditions for k-colorability, enumeration (counting) of heterogeneous and homogeneous paths, trails, cycles, and circuits in colored graphs, and a matrix-based greedy coloring algorithm. Introduced here also are the orthozeons and their application to counting monochromatic selfavoiding walks in colored graphs. The algebraic formalism easily lends itself to symbolic computations, and Mathematica-computed examples are presented throughout.

*Mathematics > Algebra