Topics in extremal graph theory

Chung, Myung Sook

Permalink

https://hdl.handle.net/2142/22749 Copy

Description

Title

Topics in extremal graph theory

Author(s)

Chung, Myung Sook

Issue Date

1993

Doctoral Committee Chair(s)

West, Douglas B.

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Mathematics

Language

eng

Abstract

• New results are proved on several problems in extremal graph theory.
• Let $ex\sp*(D;H)$ denote the maximum number of edges in a connected graph with maximum degree D and no induced subgraph isomorphic to the graph H. It is shown that this is finite if and only if H is a disjoint union of paths. Several specific forbidden subgraphs H have been studied, and the following results have been proved:
• (1) $ ex\sp*(D;P\sb4) = D\sp2$ for all D, uniquely achieved by $K\sb{D,D}.$ If, in addition, the maximum clique size is $\omega$, then the number of edges is at most $D\sp2 - {D(\omega-2)\over 2}.$
• (2) $ex\sp*(D;P\sb5) = {2\over 27}D\sp3 + O(D\sp2).$
• (3) $ex\sp*(D;2P\sb3) = {1\over 8}D\sp4 +{1\over 8}D\sp3 + O(D\sp2).$
• (4) $ex\sp*(D;P\sb3 + P\sb2)< 2D\sp2.$ If $K\sb3$ is also forbidden, then $ex\sp*(D;P\sb3 + P\sb2, K\sb3) = {5\over 4}D\sp2 + O(D).$
• The p-intersection number of a graph G, denoted by $\theta\sb{p}(G),$ is the minimum size of a set $\cup\sb{v\in V(G)}S\sb{v}$ such that u and v are adjacent if and only if $\vert S\sb{u}\cup S\sb{v}\vert \ge p.$ It is proved here that $\theta\sb{p}(K\sb{n,n})\ge (n\sp2 + (2p - 1)n)/p$ for $p\ge 2.$ Furthermore, $\theta\sb2(K\sb{n,n}) = (n\sp2 + 3n)/2$ is achieved using a graph design called orthogonal double covering. For sufficiently large p, the residual intersection number, denoted by $\theta\sp*(G),$ is defined and studied here as the limiting value of $f\sb{p}(G) = \theta\sb{p}(G)-p.$ The maximum values of n such that $\theta\sp*(K\sb{2,n}) = 5,6$ and 7 are 4, 7, and 14, respectively. Asymptotically, $\theta\sp*(K\sb{2,n}) = \log\sb2 n + o(\log\sb2 n).$
• An $(n,m,r)$-rainbow-free coloring is a multi-edge-coloring of edges in $K\sb{n}$ with at most m colors such that the edges of each color form a clique and it is not possible to choose distinct colors for each edge in any r-cycle. The maximum value of the sum of the numbers of colors appearing on each edge over all $(n,m,r)$-rainbow-free colorings, denoted by $e(n,m,r),$ was originally investigated by S. Roman. The bounds he demonstrated have been improved upon in this thesis. It is shown that $e(n,m,3) = 2{n-1\choose 2} + m - 1,$ and that $e(n,m,4)\le 3{n\choose 2} + m.$

Type of Resource

text

Permalink

http://hdl.handle.net/2142/22749

Copyright and License Information

Copyright 1993 Chung, Myung Sook

Owning Collections