- Tytuł:
- A Note on the Equitable Choosability of Complete Bipartite Graphs
- Autorzy:
-
Mudrock, Jeffrey A.
Chase, Madelynn
Thornburgh, Ezekiel
Kadera, Isaac
Wagstrom, Tim - Powiązania:
- https://bibliotekanauki.pl/articles/32325306.pdf
- Data publikacji:
- 2021-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph coloring
equitable coloring
list coloring
equitable choos-ability - Opis:
- In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A k-assignment, L, for a graph G assigns a list, L(v), of k available colors to each v ∈ V (G), and an equitable L-coloring of G is a proper coloring, f, of G such that f(v) ∈ L(v) for each v ∈ V (G) and each color class of f has size at most ⌈|V (G)|/k⌉. Graph G is said to be equitably k-choosable if an equitable L-coloring of G exists whenever L is a k-assignment for G. In this note we study the equitable choosability of complete bipartite graphs. A result of Kostochka, Pelsmajer, and West implies Kn,m is equitably k-choosable if k ≥ max{n, m} provided Kn,m ≠ K2l+1,2l+1. We prove Kn,m is equitably k-choosable if m ≤ ⌈ (m + n)/k⌉ (k − n) which gives Kn,m is equitably k-choosable for certain k satisfying k < max{n, m}. We also give a complete characterization of the equitable choosability of complete bipartite graphs that have a partite set of size at most 2.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1091-1101
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł