Characterizing almost-median graphs. II. (Q658076)

This paper is divided into four sections of which the last two discuss the kernel of the problem. While the third section deals with the convex cycles in a partial cube, Section 4 presents the main theorem, namely that if a graph \(G\) is a partial cube then \(G\) is almost-median if and only if \(G\) contains no convex cycles of length more than \(4\). This paper concludes by giving a short proof of the characterization of almost-median graphs due to \textit{I. Peterin} in his paper [``Quasi-almostmedian graphs,'' Ars Comb. (to appear)]. (For part I see [\textit{B. Brešar}, Eur. J. Comb. 28, No.\,3, 916--920 (2007; Zbl 1113.05029)].)