Maximum number of edges in graph classes under degree and matching constraints

Abstract

In extremal graph theory, we ask how large or small a property of a graph can be, when the graph has to satisfy certain constraints. In this thesis, we ask how many edges a graph can have with restrictions on its degree and matching number, when the graph belongs to a given graph class. The solutions on general graphs and bipartite graphs are known. We present here the solution on split graphs, disjoint union of split graphs and unit interval graphs. This is related to the determining the Ramsey numbers of certain graph classes. In addition, we present a characterization of factor-critical chordal graphs in terms of spanning subgraphs.

I ekstremal grafteori spør vi hvor stor eller liten en grafs egenskap kan være, gitt at den må tilfredsstille visse betingelser. In denne oppgaven, spør vi hvor mange kanter en graf kan ha når det blir satt restriksjoner på dens grad og matching tall, og grafen må tilhøre en gitt grafklasse. Løsningen på generelle og bipartite grafer er allerede kjent. Vi presenterer her løsningen på split grafer, disjunkt union av split grafer og enhetsintervall grafer. Dette er relatert til å bestemme Ramsey tall på en spesiell samling av grafer. I tillegg gir vi en karakterisering av faktor- kritiske kordale grafer ved utspennende subgrafer.