Mathematics and Statistics Vol. 11(4), pp. 733 - 737
DOI: 10.13189/ms.2023.110415
Reprint (PDF) (274Kb)

Overtrees and Their Chromatic Polynomials

Iakov M. Erusalimskiy , Vladimir A. Skorokhodov ^*
Institute of Mathematics, Mechanics and Computer Science, Southern Federal University, Russia

ABSTRACT

In this paper, graphs called overtrees are introduced and studied. These are connected graphs that contain a single simple cycle. Such graphs are connected graphs following the trees in terms of the number of edges. An overtree can be obtained from a tree by adding an edge to connect two non-adjacent vertices of a tree. The same class of graphs can also be defined as a class of graphs obtained from trees by replacing one vertex of the tree with a simple cycle. The main characteristics of overtrees are , which is the number of vertices, and , which is the number of vertices of a simple cycle (). A formula for the chromatic polynomial of an overtree is obtained, which is determined by the characteristics and only. As a consequence, it is obtained the formula for the chromatic function of a graph which is built from a tree by replacing some of its vertices (possibly all) with simple cycles of arbitrary length. It follows from these formulas that any overtree with an even-length cycle is two-colored, and with an odd-length cycle is three-colored. The same is true for graphs obtained from trees by replacing some vertices with simple cycles.

KEYWORDS
Graph, Tree, Overtree, Cycle, Coloring, Chromatic Polynomial

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Iakov M. Erusalimskiy , Vladimir A. Skorokhodov , "Overtrees and Their Chromatic Polynomials," Mathematics and Statistics, Vol. 11, No. 4, pp. 733 - 737, 2023. DOI: 10.13189/ms.2023.110415.

(b). APA Format:
Iakov M. Erusalimskiy , Vladimir A. Skorokhodov (2023). Overtrees and Their Chromatic Polynomials. Mathematics and Statistics, 11(4), 733 - 737. DOI: 10.13189/ms.2023.110415.