On maximal cycles or triangular planar polygonal graphs and their coloring. (English) Zbl 1444.05046

Jara-Vera, Vicente; Sanchez-Avila, Carmen

Int. J. Math. Comput. Sci. 16, No. 1, 185-197 (2021).

Summary: We analyze the cycles or planar polygonal graphs \(G\) which are maximal in their inner edges and offer a series of coloring results, such as \(\chi(G)=3\) or \(P(G, 3)=6\), or construction algorithms, among others. Some aspects of them with various applications in path modeling, data flow design, computer networks or best resource allocation are discussed.

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C15	Coloring of graphs and hypergraphs
05C38	Paths and cycles
68M10	Network design and communication in computer systems
94C15	Applications of graph theory to circuits and networks

Keywords:

cycle; coloring; maximal graph; network algorithm; planar graph