Frequently Asked QuestionsSubmit your Thesis or DissertationStart a New Search
#uHeader {
position: relative;
}
#headerLinks {
position: absolute;
right: 0px;
top: 50px;
}
#headerLinks > a {
margin-top: 8px;
display: block;
}
#P0_NEW_SEARCH {
font-size: 16px;
font-weight: bold;
padding-top: 10px;
}

2009, Doctor of Philosophy, Ohio State University, Mathematics.

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.

Neil Robertson (Advisor)

Akos Seress (Committee Member)

John Maharry (Committee Member)

Akos Seress (Committee Member)

John Maharry (Committee Member)

178 p.

Altomare, C. (2009). Degree Sequences, Forcibly Chordal Graphs, and Combinatorial Proof Systems. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Altomare, Christian. "Degree Sequences, Forcibly Chordal Graphs, and Combinatorial Proof Systems." Electronic Thesis or Dissertation. Ohio State University, 2009. OhioLINK Electronic Theses and Dissertations Center. 20 Jan 2018.

Altomare, Christian "Degree Sequences, Forcibly Chordal Graphs, and Combinatorial Proof Systems." Electronic Thesis or Dissertation. Ohio State University, 2009. https://etd.ohiolink.edu/