Source author record

Tim Wagstrom

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The DP Color Function of Joins and Vertex-Gluings of Graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvořák and Postle in 2015. As the analogue of the chromatic polynomial $P(G,m)$ , the DP color function of a graph $G$ , denoted $P_{DP}(G,m)$ , counts the minimum number of DP-colorings over all possible $m$ -fold covers. Chromatic polynomials for joins and vertex-gluings of graphs are well understood, but the effect of these graph operations on the DP color function is not known. In this paper we make progress on understanding the DP color function of the join of a graph with a complete graph and vertex-gluings of certain graphs. We also develop tools to study the DP color function under these graph operations, and we study the threshold (smallest $m$ ) beyond which the DP color function of a graph constructed with these operations equals its chromatic polynomial.

preprint2020arXiv

Proportional 2-Choosability with a Bounded Palette

Proportional choosability is a list coloring analogue of equitable coloring. Specifically, a $k$ -assignment $L$ for a graph $G$ specifies a list $L(v)$ of $k$ available colors to each $v \in V(G)$ . An $L$ -coloring assigns a color to each vertex $v$ from its list $L(v)$ . A proportional $L$ -coloring of $G$ is a proper $L$ -coloring in which each color $c \in \bigcup_{v \in V(G)} L(v)$ is used $\lfloor η(c)/k \rfloor$ or $\lceil η(c)/k \rceil$ times where $η(c)=\left\lvert{\{v \in V(G) : c \in L(v) \}}\right\rvert$ . A graph $G$ is proportionally $k$ -choosable if a proportional $L$ -coloring of $G$ exists whenever $L$ is a $k$ -assignment for $G$ . Motivated by earlier work, we initiate the study of proportional choosability with a bounded palette by studying proportional 2-choosability with a bounded palette. In particular, when $\ell \geq 2$ , a graph $G$ is said to be proportionally $(2, \ell)$ -choosable if a proportional $L$ -coloring of $G$ exists whenever $L$ is a $2$ -assignment for $G$ satisfying $|\bigcup_{v \in V(G)} L(v)| \leq \ell$ . We observe that a graph is proportionally $(2,2)$ -choosable if and only if it is equitably 2-colorable. As $\ell$ gets larger, the set of proportionally $(2, \ell)$ -choosable graphs gets smaller. We show that whenever $\ell \geq 5$ a graph is proportionally $(2, \ell)$ -choosable if and only if it is proportionally 2-choosable. We also completely characterize the connected proportionally $(2, \ell)$ -choosable graphs when $\ell = 3,4$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.