The Library
Kőnig's Line Coloring and Vizing's Theorems for Graphings
Tools
Csoka, Endre, Lippner, Gabor and Pikhurko, Oleg (2016) Kőnig's Line Coloring and Vizing's Theorems for Graphings. Forum of Mathematics, Sigma, 4 . e27. doi:10.1017/fms.2016.22 ISSN 2050-5094 .
PDF
WRAP_FinalVersion.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (589Kb) |
Official URL: https://doi.org/10.1017/fms.2016.22
Abstract
The classical theorem of Vizing states that every graph of maximum degree d admits an edge coloring with at most d+1 colors. Furthermore, as it was earlier shown by Kőnig, d colors suffice if the graph is bipartite. We investigate the existence of measurable edge colorings for graphings (or measure-preserving graphs). A graphing is an analytic generalization of a bounded-degree graph that appears in various areas, such as sparse graph limits, orbit equivalence and measurable group theory. We show that every graphing of maximum degree d admits a measurable edge coloring with d+O(d−−√) colors; furthermore, if the graphing has no odd cycles, then d+1 colors suffice. In fact, if a certain conjecture about finite graphs that strengthens Vizing’s theorem is true, then our method will show that d+1 colors are always enough.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Bipartite graphs, Graph theory | ||||||||
Journal or Publication Title: | Forum of Mathematics, Sigma | ||||||||
Publisher: | Cambridge University Press | ||||||||
ISSN: | 2050-5094 | ||||||||
Official Date: | 19 September 2016 | ||||||||
Dates: |
|
||||||||
Volume: | 4 | ||||||||
Article Number: | e27 | ||||||||
DOI: | 10.1017/fms.2016.22 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 25 August 2016 | ||||||||
Date of first compliant Open Access: | 25 August 2016 | ||||||||
Funder: | European Research Council (ERC), Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
Grant number: | 306493, 648017 (ERC), EP/K012045/1 (EPSRC) | ||||||||
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