The Library
Beyond Ohba’s conjecture : a bound on the choice number of k-chromatic graphs with n vertices
Tools
Tools
Tools
Noel, Jonathan A., West, Douglas B., Wu, Hehui and Zhu, Xuding (2015) Beyond Ohba’s conjecture : a bound on the choice number of k-chromatic graphs with n vertices. European Journal of Combinatorics, 43 . pp. 295-305. doi:10.1016/j.ejc.2014.08.032 ISSN 0195-6698.
|
PDF
WRAP-beyond-Ohbas-conjecture-choice-vertices-Noel-2015.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (615Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.ejc.2014.08.032
Abstract
Let ch(G) denote the choice number of a graph G (also called “list chromatic number” or “choosability” of G . Noel, Reed, and Wu proved the conjecture of Ohba that ch(G) = χ (G) when | V (G) | ≤ 2 χ (G) + 1. We extend this to a general upper bound: ch(G) ≤ max { χ (G) , ⌈ ( | V (G) | + χ (G) − 1) / 3 ⌉} . Our result is sharp for | V (G) | ≤ 3 χ (G) using Ohba’s examples, and it improves the best-known upper bound for ch( K 4 ,..., 4).
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Bipartite graphs, Graph coloring | ||||||||||||
| Journal or Publication Title: | European Journal of Combinatorics | ||||||||||||
| Publisher: | Academic Press | ||||||||||||
| ISSN: | 0195-6698 | ||||||||||||
| Official Date: | 2015 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 43 | ||||||||||||
| Page Range: | pp. 295-305 | ||||||||||||
| DOI: | 10.1016/j.ejc.2014.08.032 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| Date of first compliant deposit: | 10 July 2018 | ||||||||||||
| Date of first compliant Open Access: | 11 July 2018 | ||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
