Source author record

Paul Shin

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

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.