Source author record

Jeffrey A. Mudrock

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

9works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Maximizing Satisfied Vertex Requests in List Coloring

Suppose $G$ is a graph and $L$ is a list assignment for $G$ . A request of $L$ is a function $r$ with nonempty domain $D\subseteq V(G)$ such that $r(v) \in L(v)$ for each $v \in D$ . The triple $(G,L,r)$ is $ε$ -satisfiable if there exists a proper $L$ -coloring $f$ of $G$ such that $f(v) = r(v)$ for at least $ε|D|$ vertices in $D$ . We say $G$ is $(k, ε)$ -flexible if $(G,L',r')$ is $ε$ -satisfiable whenever $L'$ is a $k$ -assignment for $G$ and $r'$ is a request of $L'$ . It is known that a graph $G$ is not $(k, ε)$ -flexible for any $k$ if and only if $ε> 1/ ρ(G)$ where $ρ(G)$ is the Hall ratio of $G$ . The list flexibility number of a graph $G$ , denoted $χ_{\ell flex}(G)$ , is the smallest $k$ such that $G$ is $(k,1/ ρ(G))$ -flexible. A fundamental open question on list flexibility numbers asks: Is there a graph with list flexibility number greater than its coloring number? In this paper, we show that the list flexibility number of any complete multipartite graph $G$ is at most the coloring number of $G$ . We also initiate the study of list epsilon flexibility functions of complete bipartite graphs which was first suggested by Kaul, Mathew, Mudrock, and Pelsmajer in 2024. Specifically, we completely determine the list epsilon flexibility function of $K_{m,n}$ when $m \in \{1,2\}$ and establish some additional bounds for small $m$ . Our proofs reveal a connection to list coloring complete bipartite graphs with asymmetric list sizes which is a topic that was explored by Alon, Cambie, and Kang in 2021.

preprint2022arXiv

DP-Coloring Cartesian Products of Graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. Motivated by results related to list coloring Cartesian products of graphs, we initiate the study of the DP-chromatic number, $χ_{DP}$ , of the same. We show that $χ_{DP}(G \square H) \leq \text{min}\{χ_{DP}(G) + \text{col}(H), χ_{DP}(H) + \text{col}(G) \} - 1$ where $\text{col}(H)$ is the coloring number of the graph $H$ . We focus on building tools for lower bound arguments for $χ_{DP}(G \square H)$ and use them to show the sharpness of the bound above and its various forms. Our results illustrate that the DP color function of $G$ , the DP analogue of the chromatic polynomial, is essential in the study of the DP-chromatic number of the Cartesian product of graphs, including the following question that extends the sharpness problem above and the classical result on gap between list chromatic number and chromatic number: given any graph $G$ and $k \in \mathbb{N}$ , what is the smallest $t$ for which $χ_{DP}(G \square K_{k,t})= χ_{DP}(G) + k$ ?

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.

preprint2021arXiv

Partial DP-Coloring

In 1980, Albertson and Berman introduced partial coloring. In 2000, Albertson, Grossman, and Haas introduced partial list coloring. Here, we initiate the study of partial coloring for an insightful generalization of list coloring introduced in 2015 by Dvořák and Postle, DP-coloring (or correspondence coloring). We consider the DP-coloring analogue of the Partial List Coloring Conjecture, which generalizes a natural bound for partial coloring. We show that while this partial DP-coloring conjecture does not hold, several results on partial list coloring can be extended to partial DP-coloring. We also study partial DP-coloring of the join of a graph with a complete graph, and we present several interesting open questions.

preprint2020arXiv

Answers to Two Questions on the DP Color Function

DP-coloring is a generalization of list coloring that was introduced in 2015 by Dvořák and Postle. The chromatic polynomial of a graph is a notion that has been extensively studied since the early 20th century. The chromatic polynomial of graph $G$ is denoted $P(G,m)$ , and it is equal to the number of proper $m$ -colorings of $G$ . In 2019, Kaul and Mudrock introduced an analogue of the chromatic polynomial for DP-coloring; specifically, the DP color function of graph $G$ is denoted $P_{DP}(G,m)$ . Two fundamental questions posed by Kaul and Mudrock are: (1) For any graph $G$ with $n$ vertices, is it the case that $P(G,m)-P_{DP}(G,m) = O(m^{n-3})$ as $m \rightarrow \infty$ ? and (2) For every graph $G$ , does there exist $p,N \in \mathbb{N}$ such that $P_{DP}(K_p \vee G, m) = P(K_p \vee G, m)$ whenever $m \geq N$ ? We show that the answer to both these questions is yes. In fact, we show the answer to (2) is yes even if we require $p=1$ .

preprint2020arXiv

Combinatorial Nullstellensatz and DP-coloring of Graphs

We initiate the study of applying the Combinatorial Nullstellensatz to the DP-coloring of graphs even though, as is well-known, the Alon-Tarsi theorem does not apply to DP-coloring. We define the notion of good covers of prime order which allows us to apply the Combinatorial Nullstellensatz to DP-coloring. We apply these tools to DP-coloring of the cones of certain bipartite graphs and uniquely 3-colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DP-coloring. We establish a sufficient algebraic condition for a graph $G$ to satisfy $χ_{DP}(G) \leq 3$ , and we completely determine the DP-chromatic number of squares of all cycles.

preprint2020arXiv

On the Chromatic Polynomial and Counting DP-Colorings

The chromatic polynomial of a graph $G$ , denoted $P(G,m)$ , is equal to the number of proper $m$ -colorings of $G$ . The list color function of graph $G$ , denoted $P_{\ell}(G,m)$ , is a list analogue of the chromatic polynomial that has been studied since 1992, primarily through comparisons with the corresponding chromatic polynomial. DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvořák and Postle. In this paper, we introduce a DP-coloring analogue of the chromatic polynomial called the DP color function, denoted $P_{DP}(G,m)$ , and ask several fundamental open questions about it, making progress on some of them. Motivated by known results related to the list color function, we show that while the DP color function behaves similar to the list color function for some graphs, there are also some surprising differences. For example, Wang, Qian, and Yan recently showed that if $G$ is a connected graph with $l$ edges, then $P_{\ell}(G,m)=P(G,m)$ whenever $m > \frac{l-1}{\ln(1+ \sqrt{2})}$ , but we will show that for any $g \geq 3$ there exists a graph, $G$ , with girth $g$ such that $P_{DP}(G,m) < P(G,m)$ when $m$ is sufficiently large. We also study the asymptotics of $P(G,m) - P_{DP}(G,m)$ for a fixed graph $G$ . We develop techniques to compute $P_{DP}(G,m)$ exactly and apply them to certain classes of graphs such as chordal graphs, unicyclic graphs, and cycles with a chord. Finally, we make progress towards showing that for any graph $G$ , there is a $p$ such that $P_{DP}(G \vee K_p, m) = P(G \vee K_p , m)$ for large enough $m$ .

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$ .

preprint2020arXiv

Proportional Choosability of Complete Bipartite Graphs

Proportional choosability is a list analogue of equitable coloring that was introduced in 2019. The smallest $k$ for which a graph $G$ is proportionally $k$ -choosable is the proportional choice number of $G$ , and it is denoted $χ_{pc}(G)$ . In the first ever paper on proportional choosability, it was shown that when $2 \leq n \leq m$ , $\max\{ n + 1, 1 + \lceil m / 2 \rceil\} \leq χ_{pc}(K_{n,m}) \leq n + m - 1$ . In this note we improve on this result by showing that $\max\{ n + 1, \lceil n / 2 \rceil + \lceil m / 2 \rceil\} \leq χ_{pc}(K_{n,m}) \leq n + m -1- \lfloor m/3 \rfloor$ . In the process, we prove some new lower bounds on the proportional choice number of complete multipartite graphs. We also present several interesting open questions.

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.

Jeffrey A. Mudrock

Research overview

Is this your work?

9 publications

Maximizing Satisfied Vertex Requests in List Coloring

DP-Coloring Cartesian Products of Graphs

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

Partial DP-Coloring

Answers to Two Questions on the DP Color Function

Combinatorial Nullstellensatz and DP-coloring of Graphs

On the Chromatic Polynomial and Counting DP-Colorings

Proportional 2-Choosability with a Bounded Palette

Proportional Choosability of Complete Bipartite Graphs

See the researcher in context

Building this map preview