If \(G\) is \((a, b)\)-choosable, then \(G\) is \((am, bm)\)-choosable for every positive integer \(m\)
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
Choosability of graphs |
---|
A graph \( G\) is said to be \( (a,b)\)-choosable if for any assignment of a list of \( a\) colors to each of its vertices there is a subset of \( b\) colors of each list so that subsets corresponding to adjacent vertices are disjoint.
Conjecture (proposed by Erdös, Rubin, and Taylor):
If \(G\) is \( (a,b)\)-choosable, then \(G\) is \( (am,bm)\)-choosable for every positive integer \(m\).