The Diameter and the Chromatic Number of Almost Self-Complementary Graphs

Abstract

A graph $G$ with an even number of vertices is said to be
almost self-complementary if it is isomorphic to one of its
almost complements $G^c–M$, where $M$ denotes a perfect matching
in its complement $G^c$. In this paper, we show that the diameter
of connected almost self-complementary graphs must be $2$, $3$, or
$4$. Furthermore, we construct connected almost self-complementary
graphs with $2n$ vertices having diameter $3$ and $4$ for each $n\ge 3$,
and diameter $2$ for each $n\ge 4$, respectively. Additionally, we
also obtain that for any almost self-complementary graph $G_n$ with
$2n$ vertices, $\lceil \sqrt{n}\rceil \le \chi (G_n)\le n$. By
construction, we verify that the upper bound is attainable for each
positive integer $n$, as well as the lower bound when $\sqrt{n}$
is an integer.