Equitable list coloring of graphs (Q1771536): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:37, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equitable list coloring of graphs |
scientific article |
Statements
Equitable list coloring of graphs (English)
0 references
18 April 2005
0 references
Let \(G\) be a graph. Then \(G\) is equitably \(k\)-choosable if for each list assignment \(L\) so that \(\left| L(v)\right| =k\) for every vertex \(v\) of \(G\) there is a proper coloring \(\pi \) so that \(\pi (v)\in L(v),\) for all \( v\) in \(G,\) and each color appears on at most \(\left\lceil \frac{\left| G\right| }{k}\right\rceil \) vertices. \textit{A. V. Kostochka} et al. [J. Graph Theory 44, 166-177 (2003; Zbl 1031.05050)] conjectured that if \(k\geq \Delta (G)+1,\) then \(G\) is equitably \(k\)-choosable. The authors of the present paper show that the conjecture is true for all graphs of maximum degree \(3,\) and also in the case when \(k\geq (\Delta -1)^{2}.\)
0 references