Zeons, Orthozeons, and Graph Colorings

• DOI: 10.1007/s00006-016-0742-2
• Publication Date: 2016-11-23T16:19:00Z
• Authors: G. Stacey Staples; Tiffany Stellhorn
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

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 self-avoiding walks in colored graphs. The algebraic formalism easily lends itself to symbolic computations, and Mathematica-computed examples are presented throughout.