#### Date of Award

2015

#### Document Type

Open Access Thesis

#### Department

Mathematics

#### Sub-Department

College of Arts and Sciences

#### First Advisor

Linyuan Lu

#### Abstract

Let G = (V (G),E(G)) be a simple graph of order n and let i be a positive integer. X_{i} superset V (G) is called an i-packing if vertices in X_{i} are pairwise distance more than i apart. A packing coloring of G is a partition X = {X_{1},X_{2},X_{3}, . . . ,X_{k}} of V (G) such that each color class X_{i} is an i-packing. The minimum order k of a packing coloring is called the packing chromatic number of G, denoted by X_{p}(G). Let G_{n,d} denote the random d-regular graph on n vertices. In this thesis, we show that for any fixed d >= 4, there exists a positive constant c_{d} such that P(X_{p}(Gn,d) >=c_{d}n) = 1 − o_{n}(1).

#### Recommended Citation

Clifton, A. W.(2015). *The Packing Chromatic Number of Random d-regular Graphs.* (Master's thesis). Retrieved from http://scholarcommons.sc.edu/etd/3697