Proportional 2-choosability with a bounded palette

DOI10.1007/S00373-021-02448-WMaRDI QIDQ2071248zbMATH OpenOpenAlexFDO

Authors J. A. Mudrock, Robert Piechota, Paul Shin, Tim Wagstrom

Publication date 25 January 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.03418

zbMATH Keywords

equitable coloringgraph coloringlist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $vinV(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 $$ is used $lflooreta(c)/kfloor$ or $lceileta(c)/kceil$ times where $eta(c)=leftlvertvinV(G):cinL(v)ightvert$. 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 $ellgeq2$, 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 $$. 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 $ellgeq5$ 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$.

Recommendations

• Proportional choosability: a new list analogue of equitable coloring
• A simple characterization of proportionally 2-choosable graphs
• Proportional choosability of complete bipartite graphs
• A list analogue of equitable coloring
• List Coloring with a Bounded Palette

Cites work

• A list analogue of equitable coloring
• A simple characterization of proportionally 2-choosable graphs
• Coloring graphs from lists with bounded size of their union
• Equitable Coloring
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1833421 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• List Coloring with a Bounded Palette
• New global optima results for the Kauffman \(NK\) model: Handling dependency
• Perfect Graphs and an Application to Optimizing Municipal Services
• Proportional choosability: a new list analogue of equitable coloring
• The infamous upper tail

Cited in

(2)

• A simple characterization of proportionally 2-choosable graphs
• Proportional choosability of complete bipartite graphs

This page was built for publication: Proportional 2-choosability with a bounded palette

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2071248)