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

Christian Altomare1
1Department of Mathematics the Ono State Universtiy 231 WEsT 18TH AVENUE CoLuMBus, OH 43210-1174, USA

Abstract

The degree sequence of a finite graph \( G \) is its list \( D = (d_1, \ldots, 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.