We study the structure theory of two combinatorial objectsclosely related to graphs.
First, we consider degree sequences, and we prove several
results originally motivated by attempts to prove what was,
until recently, S.B. Rao's conjecture, and what is now a
theorem of Paul Seymour and Maria Chudnovsky, namely, that
graphic degree sequences are well quasi ordered. We give
a new, surprisingly non-graph theoretic proof of the bounded
case of this theorem. Next, we obtain an exact structure
theorem of degree sequences excluding a square and a pentagon.
Using this result, we then prove a structure theorem
for degree sequences excluding a square and, more generally,
excluding an arbitrary cycle. It should be noted that taking
complements, this yields a structure theorem for excluding a
matching.
The structure theorems above, however, are stated in terms of
forcibly chordal graphs, hence we next begin their
characterization. While an exact characterization seems
difficult, certain partial results are obtained. Specifically,
we first characterize the degree sequences of forcibly chordal
trees. Next, we use this result to extend the characterization to
forcibly chordal forests. Finally, we characterize forcibly
chordal graphs having a certain path structure.
Next, we define a class of combinatorial objects that generalizes
digraphs and partial orders, which is motivated by proof systems
arising in mathematical logic. We give what we believe will be
the basic theory of these objects, including definitions, theorems,
and proofs.
We define the minors of a proof system, and we give two forbidden
minors theorems, one of them characterizing partial orders as
proof systems by forbidden minors.