Sarah Loeb and Sogol Jahanbekam (UIUC Math)
Combinatorics at Mighty
Abstract:
Results in Chromatic-Paintability and the Paintability of Complete Bipartite Graphs by Sarah Loeb
Introduced independently by Schauz and by Zhu, the Marker-Remover game is an on-line version of list coloring. The game is played on a graph $G$ with a token assignment $f$ giving each $v \in V(G)$ a nonnegative number of tokens. On each round Marker marks a subset $M$ of the remaining vertices, which uses up a token on each vertex in $M$. Remover deletes from the graph an independent subset of vertices in $M$. Marker wins by marking a vertex that has no tokens. Remover wins if the entire graph is removed. The paint number, or paintability, of a graph $G$ is the least $k$ such that Remover has a winning strategy when $f(v) = k$ for all $v \in V(G)$.
We show that if $G$ is $k$-paintable and $|V(G)| \le \frac{t}{t-1} k$, then the join of $G$ with $\overline{K}_t$ is $(k+1)$-paintable. As a corollary, the paint number of $G$ equals to its chromatic number when $|V(G)| \le \chi(G) + 2 \sqrt{\chi(G)-1}$. This strengthens a result of Ohba. We also explore the paintability of complete bipartite graphs. Extending a result of Erd\H{o}s, Rubin, and Taylor, $K_{k,r}$ is $k$-paintable if and only if $r < k^k$. For $j \ge 1$ we provide an upper bound on the least $r$ such that $K_{k+j,r}$ is not $k$-paintable.
1,2,3-Conjecture and 1,2-Conjecture for sparse graphs by Sogol Jahanbekam
We apply the Discharging Method to prove the 1, 2, 3-Conjecture and the 1, 2-Conjecture for graphs with maximum average degree less than 8 3. As a result, the conjectures hold for planar graphs with girth at least 8. |
|
