Coloring count cones of planar graphs

Thumbnail Image
Date
2019-07-10
Authors
Dvorak, Zdenek
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

For a plane near-triangulation G with the outer face bounded by a cycle C, let n⋆G denote the function that to each 4-coloring ψ of C assigns the number of ways ψ extends to a 4-coloring of G. The block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function n⋆G belongs to a certain cone in the space of all functions from 4-colorings of C to real numbers. We investigate the properties of this cone for |C|=5, formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture.

Series Number
Journal Issue
Is Version Of
Article
Coloring count cones of planar graphs
(Wiley Periodicals LLC, 2022-05) Dvořák, Zdeněk ; Lidicky, Bernard ; Department of Mathematics
For a plane near‐triangulation G with the outer face bounded by a cycle C, let nG⋆ denote the function that to each 4‐coloring ψ of C assigns the number of ways ψ extends to a 4‐coloring of G. The Block‐count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function nG⋆ belongs to a certain cone in the space of all functions from 4‐colorings of C to real numbers. We investigate the properties of this cone for |C| = 5, formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture.
Versions
Series
Academic or Administrative Unit
Type
article
Comments

This is a pre-print made available through arxiv: https://arxiv.org/abs/1907.04066.

Rights Statement
Copyright
Tue Jan 01 00:00:00 UTC 2019
Funding
DOI
Supplemental Resources
Source
Collections