×

Zeons, orthozeons, and graph colorings. (English) Zbl 1365.05103

Summary: 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Albert, M., Frieze, A., Reed, B.: Multicolored Hamilton cycles. Electron. J. Combin.2, #R10 (1995) · Zbl 0817.05028
[2] Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer’s Theorem. In: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29-September 2, 2005. Proceedings, Jȩdrzejowicz, J., Szepietowski, A. (Eds.), Springer, Berlin, 2005, pp. 71-82. doi:10.1007/11549345_8 · Zbl 1156.68396
[3] Babu, J., Chandran, S., Rajendraprasad, D.: Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs. Eur. J. Combin. 48, 110-126 (2015). doi:10.1016/j.ejc.2015.02.014 · Zbl 1315.05046
[4] Ben Slimane, J., Schott, R., Song, Y.-Q., Staples, G.S., Tsiontsiou, E.: Operator calculus algorithms for multi-constrained paths. Int. J. Math. Comput. Sci. 10, 69-104 (2015). http://ijmcs.future-in-tech.net/10.1/R-Jamila. Accessed 19 Nov 2016 · Zbl 1397.05192
[5] Broersma, H.J., Li, X.L., Woeginger, G., Zhang, S.G.: Paths and cycles in colored graphs. Aust. J. Combin. 31, 297-309 (2005) · Zbl 1061.05030
[6] Budinich, M., Budinich, P.: A spinorial formulation of the maximum clique problem of a graph. J. Math. Phys. 47, 043502 (2006) · Zbl 1111.05073 · doi:10.1063/1.2186256
[7] Chen, H., Li, X.: Long heterochromatic paths in edge-colored graphs. Electron. J. Combin. 12, #R33 (2005) · Zbl 1080.05047
[8] Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151-158. doi:10.1145/800157.805047 · Zbl 0511.05046
[9] Cruz-Sánchez, H., Staples, G.S., Schott, R., Song, Y.-Q.: Operator calculus approach to minimal paths: Precomputed routing in a store-and-forward satellite constellation. In: Proceedings of IEEE Globecom 2012, Anaheim, CA, USA, December 3-7, 3455-3460. ISBN: 978-1-4673-0919-6 · Zbl 0511.05046
[10] Erdös, P., Tuza, Z.S.: Rainbow Hamiltonian paths and canonically colored subgraphs in infinite complete graphs. Math. Pannon. 1, 5-13 (1990) · Zbl 0724.05048
[11] Erdös, P., Tuza, Z.S.: Rainbow subgraphs in edge-colorings of complete graphs. Ann. Discr. Math. 55, 81-88 (1993) · Zbl 0791.05037 · doi:10.1016/S0167-5060(08)70377-7
[12] Frieze, A.M., Reed, B.A.: Polychromatic Hamilton cycles. Discr. Math. 118, 69-74 (1993) · Zbl 0803.05036 · doi:10.1016/0012-365X(93)90054-W
[13] Gyáfás, A.: Vertex coverings by monochromatic paths and cycles. J. Graph Theory 7, 131-135 (1983) · Zbl 0511.05046 · doi:10.1002/jgt.3190070116
[14] Harris, G., Staples, G.S.: Spinorial formulations of graph problems. Adv. Appl. Clifford Algebra. 22, 59-77 (2012). doi:10.1007/s00006-011-0298-0 · Zbl 1266.15036
[15] Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations, Miller, R.E., Thatcher, J.W. (Eds.), The IBM Research Symposia Series, New York, NY: Plenum Press, pp. 85-103 (1972) · Zbl 1467.68065
[16] Li, X., Zhang, S., Broersma, H.: Paths and cycles in colored graphs. Electron. Note Discr. Math. 8, 128-132 (2001) · Zbl 1412.05070 · doi:10.1016/S1571-0653(05)80098-8
[17] Nefzi, B., Schott, R., Song, Y.-Q., Staples, G.S., Tsiontsiou, E.: An operator calculus approach for multi-constrained routing in wireless sensor networks, ACM MobiHoc: Hangzhou. China, To appear (2015) · Zbl 1111.05073
[18] Neto, A.F.: Higher order derivatives of trigonometric functions, Stirling numbers of the second kind, and zeon algebra. J. Integer Seq. 17, Article 14.9.3 (2014) · Zbl 1358.11044
[19] Neto, A.F.: Carlitz’s identity for the Bernoulli numbers and zeon algebra. J. Integer Seq. 18, Article 15.5.6 (2015) · Zbl 1378.11034
[20] Neto, A.F.: A note on a theorem of Guo, Mezö, and Qi. J. Int. Seq. 19, Article 16.4.8 (2016) · Zbl 1415.11041
[21] Neto, A.F., dos Anjos, P.H.R.: Zeon algebra and combinatorial identities. SIAM Rev. 56, 353-370 (2014) · Zbl 1292.05051 · doi:10.1137/130906684
[22] Raynaud, H.: Sur le circuit hamiltonien hi-colore dans les graphes orientes. Periodica Math. Hung. 3, 289-297 (1973) · Zbl 0267.05114 · doi:10.1007/BF02018596
[23] Schaefer, T.J.: The complexity of satisfiability problems. In: STOC ’78 Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ACM New York, NY, pp. 216-226 (1978). doi:10.1145/800133.804350 · Zbl 1282.68143
[24] Schott, R., Staples, G.S.: Partitions and Clifford algebras. Eur. J. Comb. 29, 1133-1138 (2008) · Zbl 1149.05005 · doi:10.1016/j.ejc.2007.07.003
[25] Schott, R., Staples, G.S.: Zeons, lattices of partitions, and free probability. Comm. Stoch. Anal. 4, 311-334 (2010) · Zbl 1331.46058
[26] Schott, R., Staples, G.S.: Operator Calculus on Graphs (Theory and Applications in Computer Science). Imperial College Press, London (2012) · Zbl 1264.15025 · doi:10.1142/p843
[27] Staples, G.S.: A new adjacency matrix for finite graphs. Adv. Appl. Clifford Algebras 18, 979-991 (2008). doi:10.1007/s00006-008-0116-5 · Zbl 1194.05099 · doi:10.1007/s00006-008-0116-5
[28] West, D.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.