Show simple item record

dc.contributor.author
Hertrich, Christoph
dc.contributor.author
Schröder, Felix
dc.contributor.author
Steiner, Raphael
dc.date.accessioned
2023-01-25T11:02:18Z
dc.date.available
2023-01-17T15:37:12Z
dc.date.available
2023-01-25T11:02:18Z
dc.date.issued
2022
dc.identifier.issn
1097-1440
dc.identifier.issn
1077-8926
dc.identifier.other
10.37236/9808
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/593124
dc.identifier.doi
10.3929/ethz-b-000593124
dc.description.abstract
We consider cell colorings of drawings of graphs in the plane. Given a multi-graphGtogether with a drawing Γ(G) in the plane with only finitely many crossings,we define acellk-coloringof Γ(G) to be a coloring of the maximal connected regionsof the drawing, thecells, withkcolors such that adjacent cells have different colors.By the 4-color theorem, every drawing of a bridgeless graph has a cell 4-coloring.A drawing of a graph is cell 2-colorable if and only if the underlying graph isEulerian. We show that every graph without degree 1 vertices admits a cell 3-colorable drawing. This leads to the natural question whichabstractgraphs havethe property that each of their drawings has a cell 3-coloring. We say that such agraph isuniversally cell3-colorable. We show that every 4-edge-connected graphand every graph admitting anowhere-zero3-flowis universally cell 3-colorable. Wealso discuss circumstances under which universal cell 3-colorability guarantees theexistence of a nowhere-zero 3-flow. On the negative side, we present an infinitefamily of universally cell 3-colorable graphs without a nowhere-zero 3-flow. On thepositive side, we formulate a conjecture which has a surprising relation to a famousopen problem by Tutte known as the 3-flow-conjecture. We prove our conjecturefor subcubic and forK3,3-minor-free graphs.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Electronic Journal of Combinatorics
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.title
Coloring Drawings of Graphs
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2022-01-28
ethz.journal.title
The Electronic Journal of Combinatorics
ethz.journal.volume
29
en_US
ethz.journal.issue
1
en_US
ethz.journal.abbreviated
J. comb.
ethz.pages.start
P1.17
en_US
ethz.size
35 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.publication.place
Clemson, SC
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
en_US
ethz.date.deposited
2023-01-17T15:37:13Z
ethz.source
FORM
ethz.eth
no
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2023-01-25T11:02:19Z
ethz.rosetta.lastUpdated
2023-02-07T10:03:36Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Coloring%20Drawings%20of%20Graphs&rft.jtitle=The%20Electronic%20Journal%20of%20Combinatorics&rft.date=2022&rft.volume=29&rft.issue=1&rft.spage=P1.17&rft.issn=1097-1440&1077-8926&rft.au=Hertrich,%20Christoph&Schr%C3%B6der,%20Felix&Steiner,%20Raphael&rft.genre=article&rft_id=info:doi/10.37236/9808&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record