A simple characterization of proportionally 2-choosable graphs

DOI10.1007/S00373-020-02146-ZMaRDI QIDQ2175799zbMATH OpenOpenAlexFDO

Authors Hemanshu Kaul, J. A. Mudrock, Michael J. Pelsmajer, Benjamin Reiniger

Publication date 30 April 2020

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

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

zbMATH Keywords

equitable choosabilityequitable coloringgraph coloringlist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We recently introduced proportional choosability, a new list analogue of equitable coloring. Like equitable coloring, and unlike list equitable coloring (a.k.a. equitable choosability), proportional choosability bounds sizes of color classes both from above and from below. In this note, we show that a graph is proportionally 2-choosable if and only if it is a linear forest such that its largest component has at most 5 vertices and all of its other components have two or fewer vertices. We also construct examples that show that characterizing equitably 2-choosable graphs is still open.

Recommendations

• Proportional 2-choosability with a bounded palette
• Proportional choosability: a new list analogue of equitable coloring
• Proportional choosability of complete bipartite graphs
• A list analogue of equitable coloring
• Equitable coloring and equitable choosability of graphs with small maximum average degree

Cites work

• A list analogue of equitable coloring
• Equitable and equitable list colorings of graphs
• Equitable Coloring
• Equitable list coloring of graphs
• Equitable list coloring of graphs with bounded degree
• Equitable list coloring of planar graphs without 4- and 6-cycles
• Equitable list colorings of planar graphs without short cycles
• Equitable list-coloring for \(C_{5}\)-free plane graphs without adjacent triangles
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1833421 (Why is no real title available?)
• New global optima results for the Kauffman \(NK\) model: Handling dependency
• On equitable and equitable list colorings of series-parallel graphs
• Perfect Graphs and an Application to Optimizing Municipal Services
• Proportional choosability: a new list analogue of equitable coloring
• The infamous upper tail

Cited in

(3)

• Proportional 2-choosability with a bounded palette
• On the equitable choosability of the disjoint union of stars
• Proportional choosability of complete bipartite graphs

This page was built for publication: A simple characterization of proportionally 2-choosable graphs

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