Thursday, July 21 2022

3:30pm - 5:30pm

3:30pm - 5:30pm

PhD Thesis Presentation

Degree Sequence Realization Problems for Hypergraphs and Applications of the Discharging Method to Entire Coloring

Abstract: The first part of this thesis involves realization problems for degree sequences in a hypergraph context. A graphic sequence $/pi$ is potentially $H$-graphic if there is a realization of $\pi$ contains $G$ as a subgraph. The potential number, $\sigma (H,n)$, is the minimum even integer such that any graphic sequence with length $n$ and sum greater than $\sigma (H,n)$ is potentially $H$-graphic. In this paper we extend these notions to $3$-uniform hypergraphs and determine the potential number for $3$-uniform hypercliques. We also discuss the stability of the potential number in the $r=3$ case.

The second part of this thesis deals with the discharging method and entire coloring of planar graphs. Let $G$ be a plane graph with maximum degree $\Delta$. If all vertices, edges, and faces of $G$ can be colored with $k$ colors so that any two adjacent or incident elements have distinct colors, then $G$ is said to be entirely $k$-colorable. In 2011, Wang and Zhu asked if every simple plane graph except $K_4$ is entirely $(\Delta+3)$-colorable. In 2012, Wang, Mao, and Miao answered in the affirmative for simple plane graphs with $\Delta \geq 8$.

In this paper, we show that every plane multigraph with $\Delta=7$, no loops, no 2-faces, and no 3-faces sharing an edge is entirely $(\Delta+3)$-colorable.

The second part of this thesis deals with the discharging method and entire coloring of planar graphs. Let $G$ be a plane graph with maximum degree $\Delta$. If all vertices, edges, and faces of $G$ can be colored with $k$ colors so that any two adjacent or incident elements have distinct colors, then $G$ is said to be entirely $k$-colorable. In 2011, Wang and Zhu asked if every simple plane graph except $K_4$ is entirely $(\Delta+3)$-colorable. In 2012, Wang, Mao, and Miao answered in the affirmative for simple plane graphs with $\Delta \geq 8$.

In this paper, we show that every plane multigraph with $\Delta=7$, no loops, no 2-faces, and no 3-faces sharing an edge is entirely $(\Delta+3)$-colorable.

Speaker: | Nathan Graber |

Affiliation: | |

Location: | Zoom in email |

Done