The Library
Third case of the cyclic coloring conjecture
Tools
Hebdige, Michael and Králʼ, Daniel (2016) Third case of the cyclic coloring conjecture. SIAM Journal on Discrete Mathematics, 30 (1). pp. 525-548. doi:10.1137/15M1019490 ISSN 0895-4801.
|
PDF
WRAP_cyclic_coloring_Hebdige_Kral_2016_published_version.pdf - Published Version - Requires a PDF viewer. Download (560Kb) | Preview |
|
PDF
WRAP_1173667-ma-120116-cyclic-six.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (298Kb) |
Official URL: http://dx.doi.org/10.1137/15M1019490
Abstract
The Cyclic Coloring Conjecture asserts that the vertices of every plane graph with maximum face size $\Delta^*$ can be colored using at most $\lfloor3\Delta^*/2\rfloor$ colors in such a way that no face is incident with two vertices of the same color. The Cyclic Coloring Conjecture has been proven only for two values of $\Delta^*$: the case $\Delta^*=3$ is equivalent to the Four Color Theorem and the case $\Delta^*=4$ is equivalent to Borodin's Six Color Theorem, which says that every graph that can be drawn in the plane with each edge crossed by at most one other edge is 6-colorable. We prove the case $\Delta^*=6$ of the conjecture.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||
ISSN: | 0895-4801 | ||||||||
Official Date: | 24 March 2016 | ||||||||
Dates: |
|
||||||||
Volume: | 30 | ||||||||
Number: | 1 | ||||||||
Number of Pages: | 28 | ||||||||
Page Range: | pp. 525-548 | ||||||||
DOI: | 10.1137/15M1019490 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 19 January 2016 | ||||||||
Date of first compliant Open Access: | 29 March 2016 | ||||||||
Funder: | ERC | ||||||||
Grant number: | 259385 | ||||||||
Related URLs: | |||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year