Triangle-Free Polyconvex Graphs

Abstract

The notion of convexity in graphs is based on the one in topology: a set of vertices $S$ is convex if an interval is entirely contained in $S$ when its endpoints belong to $S$. The order of the largest proper convex subset of a graph $G$ is called the convexity number of the graph and is denoted $con(G)$. A graph containing a convex subset of one order need not contain convex subsets of all smaller orders. If $G$ has convex subsets of order $m$ for all $1\le m\le con(G)$, then $G$ is called polyconvex. In response to a question of Chartrand and Zhang [3], we show that, given any pair of integers $n$ and $k$ with $2\le k<n$, there is a connected triangle-free polyconvex graph $G$ of order $n$ with convexity number $k$.