Document detail
ID
oai:arXiv.org:2303.05583
Topic
Mathematics - Combinatorics Computer Science - Discrete Mathem...Author
Bang, Caroline Dvořák, Zdeněk Heath, Emily Lidický, BernardCategory
Computer Science
Year
2023
listing date
3/15/2023
Abstract
A graph drawn in a surface is a near-quadrangulation if the sum of the lengths of the faces different from 4-faces is bounded by a fixed constant.
We leverage duality between colorings and flows to design an efficient algorithm for 3-precoloring-extension in near-quadrangulations of orientable surfaces.
Furthermore, we use this duality to strengthen previously known sufficient conditions for 3-colorability of triangle-free graphs drawn in orientable surfaces.
;Comment: 53 pages, 15 figures
Bang, Caroline,Dvořák, Zdeněk,Heath, Emily,Lidický, Bernard, 2023, Embedded graph 3-coloring and flows
Is one brick enough to break the wall of spoken dialogue state tracking?
approach spoken approaches [cs dialogue science [info
