UC Berkeley

We investigate three graph polynomials including antimagic, super edge-magic, and chromatic polynomials. The Antimagic Graph Conjecture asserts that every connected graph $G = (V,E)$ except $K_2$ admits an edge labeling such that each label $1,2,\ldots,|E|$ is used exactly once and the sums of the labels of the edges incident to each vertex are distinct. We introduce partially magic labelings where the vertex sums are the same in a subset of $V$. By using the quasi-polynomial structure of the partially magic labeling counting function, we show that every bipartite graph satisfies a relaxed version of the Antimagic Graph Conjecture (that is, repetition of labels are allowed). \

A total labeling $f:E \cup V \to \ZZ_{\ge 0}$ of a graph $G=(V,E)$ is called \emph{super edge-magic} if each vertex label is in $\{1,\ldots, |V|\}$ and the sum of the edge label plus labels of its two ends is the same for all edges of $G$. We prove that the counting function of super edge-magic labelings of every tree is a polynomial. This helps us to show that every tree admits a relaxed super edge magic labeling which is the relaxed version of \emph{Super Edge-Magic Tree Conjecture}. Moreover, we show that every tree with one extra edge that makes a unique even cycle admits a super edge-magic labeling. On the other hand, a \emph{harmonious labeling} is an injective function $L:V \rightarrow \{0, 1, \ldots, |E|-1 \}$ such that the induced edge labels $L^{*}(e) \equiv L(u)+L(v)$ (mod $|E|$) for every edge $e=\{u,v\} \in E,$ are distinct. The \emph{Harmonious Tree Conjecture} indicates that every tree admits a harmonious labeling. We use our results on super edge-magic labelings to prove that every tree admits a relaxed version of the Harmonious Tree Conjecture. \

Lastly, we extend classic order polynomials to a two variable version and we drive a reciprocity theorem for strict and weak order polynomials, reminiscent of Stanley's reciprocity theorem. We also study the \emph{bivariate chromatic polynomial} which counts the number of vertex coloring of $G$ with $1 \le x$ colors allowing the same colors for adjacent vertices if the color is $\ge y$ ($1 \le y \le x$). We decompose bivariate chromatic polynomial into bivariate order polynomials and we find a reciprocity relation linking bivariate chromatic polynomials to acyclic orientations.