### Journals Information

**
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.