-
Coloring-flow duality of embedded graphsDevos, Matt ...Let ▫$G$▫ be a directed graph embedded in a surface. A map ▫$\phi: E(G) \rightarrow \mathbb{R}$▫ is a tension if for every circuit ▫${\mathcal C} \subseteq G$▫, the sum of ▫$\phi$▫ on the forward ... edges of ▫${\mathcal C}$▫ is equal to the sum of ▫$\phi$▫ on the backward edges of ▫${\mathcal C}$▫. If this condition is satisfied for every circuit of ▫$G$▫ which is contractible curve in the surface, then ▫$\phi$▫ is a local tension. If ▫$1 \le |\phi(e)| \le \alpha - 1$▫ holds for every ▫$e \in E(G)$▫, we say that ▫$\phi$▫ is a (local) ▫$\alpha$▫-tension. We define the circular chromatic number and the local circular chromatic number of ▫$G$▫ by ▫$\chi_{\mathcal{C}}(G) = \inf \{ \alpha \in \mathbb{R} \; | \;G \; \textrm{has an} \;\alpha-\textrm{tension}\}$▫ and ▫$\chi_{\textrm{loc}}(G) = \inf \{ \alpha \in \mathbb{R} \; | \; G \; \textrm{has a local} \; \alpha-\textrm{tension}\}$▫, respectively. The invariant ▫$\chi_{\mathcal{C}}$▫ is a refinement of the usual chromatic number, whereas ▫$\chi_{\textrm{loc}}$▫ is closed related to Tutte's flow index and Bouchet's biflow index of the surface dual ▫$G^\ast$▫. From the definitions we have ▫$\chi_{\textrm{loc}}(G) \le \chi_{\mathcal{C}}(G)$▫. The main result of this paper is a far reaching generalization of Tutte's coloring flow-duality in planar graphs. It is proved that for every surface ▫$\mathbb{X}$▫ and every ▫$\varepsilon > 0$▫, there exist an integer ▫$M$▫ so that ▫$\chi_{\mathcal{C}}(G) \le \chi_{\textrm{loc}}(G) + \varepsilon$▫ holds for every graph embedded in ▫$\mathbb{X}$▫ with edge-width at least ▫$M$▫, where the edge-width is the length of a shortest noncontractible circuit in ▫$G$▫. In 1996, Youngs discovered that every quadrangulation of the projective plane has chromatic number 2 or 4, but never 3. As an application of the main result we show that such "bimodal" behavior can be observed in ▫$\chi_{\textrm{loc}}$▫, and thus in ▫$\chi_{\mathcal{C}}$▫ for two generic classes of embedded graphs: those that are triangulations and those whose face boundaries all have even length. In particular, if ▫$G$▫ is embedded in some surface with large edge width and all its faces have even length ▫$\le 2r$▫, then ▫$\chi_{\mathcal{C}}(G) \in [2,2 + \varepsilon] \cup [\frac{2r}{r-1},4]$▫. Similarly, if ▫$G$▫ is a triangulation with large edge-width, then ▫$\chi_{\mathcal{C}}(G) \in [3,3 + \varepsilon] \cup [4,5]$▫. It is also shown that there exist Eulerian triangulations of arbitrary large edge-width on nonoriantable surfaces whose circular chromatic number is equal to 5.Source: Transactions of the American Mathematical Society. - ISSN 0002-9947 (Vol. 357, No. 10, 2005, str. 3993-4016)Type of material - article, component partPublish date - 2005Language - englishCOBISS.SI-ID - 13781081
Author
Devos, Matt |
Goddyn, Luis |
Mohar, Bojan, 1956- |
Vertigan, Dirk |
Zhu, Xuding
Topics
matematika |
teorija grafov |
barvanje |
pretok |
napetost |
lokalna napetost |
krožno kromatično število |
ploskev |
povezavna širina |
triangulacija |
kvadrangulacija |
lokalna dvodelnost |
mathematics |
graph theory |
coloring |
flow |
tension |
local tension |
circular chromatic number |
surface |
edge-width |
triangulation |
quadrangulation |
locally bipartite
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Devos, Matt | ![]() |
Goddyn, Luis | ![]() |
Mohar, Bojan, 1956- | 01931 |
Vertigan, Dirk | ![]() |
Zhu, Xuding | ![]() |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.