IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Lower Bound for the Packing Chromatic Number of Cubic Graphs

  • Oct. 31, 2014
  • 2:30 p.m.
  • LeConte 312


Let $G = (V,E)$ be a simple graph of order $n$ and let $i$ be an integer with $i \geq 1$. The set $X _ i \subseteq 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, \dots, 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 $\chi _ \rho(G)$. In this talk we show if $G$ is a simple cubic graph, then $\chi _ \rho(G) \geq 4$ with equality holding if and only if $G = K _ 4$ or $G = K _ {3,3}$.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster