Extremal problems involving forbidden subgraphs

Kim, Jaehoon

Permalink

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

Description

Title

Extremal problems involving forbidden subgraphs

Author(s)

Kim, Jaehoon

Issue Date

2014-05-30T16:46:19Z

Director of Research (if dissertation) or Advisor (if thesis)

Kostochka, Alexandr V.

Doctoral Committee Chair(s)

Weichsel, Paul M.

Committee Member(s)

• Kostochka, Alexandr V.
• West, Douglas B.
• Lidicky, Bernard

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Extremal Graph Theory
• Graphs
• Graph Coloring
• Hypergraphs
• Forbidden Subgraphs

Abstract

In this thesis, we study extremal problems involving forbidden subgraphs. We are interested in extremal problems over a family of graphs or over a family of hypergraphs. In Chapter 2, we consider improper coloring of graphs without short cycles. We find how sparse an improperly critical graph can be when it has no short cycle. In particular, we find the exact threshold of density of triangle-free $(0,k)$-colorable graphs and we find the asymptotic threshold of density of $(j,k)$-colorable graphs of large girth when $k\geq 2j+2$. In Chapter 3, we consider other variations of graph coloring. We determine harmonious chromatic number of trees with large maximum degree and show upper bounds of $r$-dynamic chromatic number of graphs in terms of other parameters. In Chapter 4, we consider how dense a hypergraph can be when we forbid some subgraphs. In particular, we characterize hypergraphs with the maximum number of edges that contain no $r$-regular subgraphs. We also establish upper bounds for the number of edges in graphs and hypergraphs with no edge-disjoint equicovering subgraphs.

Graduation Semester

2014-05

Permalink

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

Copyright and License Information

Copyright 2014 Jaehoon Kim

Owning Collections