The Packing Chromatic Number of Random d-regular Graphs

Author

Ann Wells Clifton, University of South Carolina

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₁,X₂,X₃, . . . ,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_dn) = 1 − o_n(1).

Rights

© 2015, Ann Wells Clifton

Recommended Citation

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