Jeffrey A. Mudrock

Cones of Theta Graphs are Enumeratively Chromatic-Choosable

Kingston Barnes, Vincent Fesenmeier, Braxton Gaither +7

Chromatic choosability is a fundamental notion in list coloring. A graph $G$ is chromatic-choosable if its chromatic number $χ (G)$ equals its list chromatic number $χ_{ℓ} (G)$ . I…

Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs

Hemanshu Kaul, Jeffrey A. Mudrock, Emily A. Psyhogios +3

A famous folklore result in list coloring demonstrating that the gap between the list chromatic number and chromatic number of a graph can be arbitrarily large is: $χ_{\ell}(K_{l,t…

The DP Color Function of Bipartite Graphs

Hemanshu Kaul, Jeffrey A. Mudrock, Gunjan Sharma +1

DP-coloring (or correspondence coloring) is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in 2015. As the analogue of $…

The unlabeled list color function of disconnected graphs

Hemanshu Kaul, Jeffrey A. Mudrock, Armin Straub

Given a graph $G$ , its chromatic polynomial $P (G, k)$ counts proper $k$ -colorings, while the corresponding list color function $P_{ℓ} (G, k)$ counts the minimum number of prope…

Enumeratively Chromatic-Choosable Theta Graphs

Yanghong Chi, Seoju Lee, Fennec Morrissette +3

Chromatic choosability is a notion of fundamental importance in list coloring. A graph $G$ is chromatic-choosable when its chromatic number, $χ (G)$ , is equal to its list chromatic…

Fractional Strict Degeneracy of Graphs

Daniel Dominik, Jeffrey A. Mudrock

DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. The DP-chromatic number of a graph $G$ , $χ_{_{DP}}(G…

An Ohba-like Result for Flexible List Coloring

Michael C. Bowdoin, Yanghong Chi, Christian B. Ellington +4

Chromatic-choosability is a notion of fundamental importance in list coloring. A graph $G$ is chromatic-choosable when its chromatic number, $χ (G)$ , is equal to its list chromatic…

List Coloring the Cartesian Product of a Complete Graph and Complete Bipartite Graph

Hemanshu Kaul, Leonardo Marciaga, Jeffrey A. Mudrock

We study the list chromatic number of the Cartesian product of a complete graph of order $n$ and a complete bipartite graph with partite sets of size $a$ and $b$ , denoted $χ_{\ell}…

On the DP-chromatic Number of Cartesian Products of Critical Graphs

Hemanshu Kaul, Jeffrey A. Mudrock, Gunjan Sharma

DP-coloring (also called correspondence coloring) is a well-studied generalization of list coloring introduced by Dvořák and Postle in 2015. The following sharp bound on the DP-chr…

Enumerative Chromatic Choosability

Sarah Allred, Jeffrey A. Mudrock

Chromatic-choosablility is a notion of fundamental importance in list coloring. A graph is chromatic-choosable when its chromatic number is equal to its list chromatic number. In 1…

Shameful Inequalities for List and DP Coloring of Graphs

Hemanshu Kaul, Jeffrey A. Mudrock, Gunjan Sharma

The chromatic polynomial of a graph is an important notion in algebraic combinatorics that was introduced by Birkhoff in 1912; denoted $P (G, k)$ , it equals the number of proper $k$ -…

Maximizing Satisfied Vertex Requests in List Coloring

Timothy Bennett, Michael C. Bowdoin, Haley Broadus +5

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

Counting List Colorings of Unlabeled Graphs

Hemanshu Kaul, Jeffrey A. Mudrock

The classic enumerative functions for counting colorings of a graph $G$ , such as the chromatic polynomial $P (G, k)$ , do so under the assumption that the given graph is labeled. In 1…

On strongly and robustly critical graphs

Anton Bernshteyn, Hemanshu Kaul, Jeffrey A. Mudrock +1

In extremal combinatorics, it is common to focus on structures that are minimal with respect to a certain property. In particular, critical and list-critical graphs occupy a promin…

On Polynomial Representations of Dual DP Color Functions

Jeffrey A. Mudrock, Gabriel Sharbel

DP-coloring (also called correspondence coloring) is a generalization of list coloring that was introduced by Dvořák and Postle in 2015. The chromatic polynomial of a graph is an i…

On the Ohba Number and Generalized Ohba Numbers of Complete Bipartite Graphs

Kennedy Cano, Emily Gutknecht, Gautham Kappaganthula +3

We say that a graph $G$ is chromatic-choosable when its list chromatic number $χ_{ℓ} (G)$ is equal to its chromatic number $χ (G)$ . Chromatic-choosability is a well-studied topic,…

Counting Packings of List-colorings of Graphs

Hemanshu Kaul, Jeffrey A. Mudrock

Given a list assignment for a graph, list packing asks for the existence of multiple pairwise disjoint list colorings of the graph. Several papers have recently appeared that study…

math.CO2023

A Polynomial Method for Counting Colorings of Sparse Graphs

Samantha L. Dahlberg, Hemanshu Kaul, Jeffrey A. Mudrock

The notion of $S$ -labeling of graphs, where $S$ is a subset of a symmetric group, was introduced in 2019 by Jin, Wong, and Zhu. This notion provides the framework for a common gene…

math.CO2023

DP-Coloring of Graphs from Random Covers

Anton Bernshteyn, Daniel Dominik, Hemanshu Kaul +1

DP-coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in $2015$ .…

An Algebraic Approach for Counting DP-3-colorings of Sparse Graphs

Samantha L. Dahlberg, Hemanshu Kaul, Jeffrey A. Mudrock

DP-coloring (or correspondence coloring) is a generalization of list coloring that has been widely studied since its introduction by Dvořák and Postle in 2015. As the analogue of t…

Flexible list colorings: Maximizing the number of requests satisfied

Hemanshu Kaul, Rogers Mathew, Jeffrey A. Mudrock +1

Flexible list coloring was introduced by Dvořák, Norin, and Postle in 2019. Suppose $0 \leq ε \leq 1$ , $G$ is a graph, $L$ is a list assignment for $G$ , and $r$ is a function with n…

A Short Proof that the List Packing Number of any Graph is Well Defined

Jeffrey A. Mudrock

List packing is a notion that was introduced in 2021 (by Cambie et al.). The list packing number of a graph $G$ , denoted $χ_{ℓ}^{*} (G)$ , is the least $k$ such that for any list as…

Bounding the List Color Function Threshold from Above

Hemanshu Kaul, Akash Kumar, Andrew Liu +5

The chromatic polynomial of a graph $G$ , denoted $P (G, m)$ , is equal to the number of proper $m$ -colorings of $G$ for each $m \in N$ . In 1990, Kostochka and Sidorenko intro…