11 papers
An Improved Algorithm for Finding Maximum Outerplanar Subgraphs
Gruia Calinescu, Hemanshu Kaul, Bahareh Kudarzi
We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2/3. We propose a new approximation algorithm which i…
Non-chromatic-adherence of the DP Color Function via Generalized Theta Graphs
Manh Vu Bui, Hemanshu Kaul, Michael Maxfield +3
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 2…
Partial DP-Coloring
Hemanshu Kaul, Jeffrey A. Mudrock, Michael J. Pelsmajer
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…
Combinatorial Nullstellensatz and DP-coloring of Graphs
Hemanshu Kaul, Jeffrey A. Mudrock
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…
On the Chromatic Polynomial and Counting DP-Colorings
Hemanshu Kaul, Jeffrey A. Mudrock
The chromatic polynomial of a graph , denoted , is equal to the number of proper -colorings of . The list color function of graph , denoted , is…
List Coloring a Cartesian Product with a Complete Bipartite Factor
Hemanshu Kaul, Jeffrey A. Mudrock
We study the list chromatic number of the Cartesian product of any graph and a complete bipartite graph with partite sets of size and , denoted $χ_\ell(G \square K_{a,b}…