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 \leq m \leq 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 \leq k < n\), there is a connected triangle-free polyconvex graph \(G\) of order \(n\) with convexity number \(k\).