A Note on Graphic Sequences with No Realization Containing an Induced Four Cycle

Abstract

The degree sequence of a finite graph $G$ is its list $D=(d_1,\dots ,d_n)$ of vertex degrees in non-increasing order. The graph $G$ is called a realization of $D$. In this paper, we characterize the graphic degree sequences $D$ such that no realization of $D$ contains an induced four-cycle. Our characterization is stated in terms of the class of forcibly chordal graphs.