Atlas Mathematical Conference Abstracts ||
Conferences |
Abstracts |
for Organizers |
About AMCA
Horizons in Combinatorics/16th Shanks Lecture Series
May 21-24, 2001
Vanderbilt University
Nashville, TN, USA |
|
Organizers
Paul Edelman, Mark Ellingham, Jonathan Farley, Mike Plummer, Jerry Spinrad
View Abstracts
Conference Homepage |
Near duality of circular coloring and circular flow in orientable surfaces.
by
Dirk Vertigan
Louisiana State University
Coauthors: Matt Devos, (Rice University, Rice University, Houston, Texas, USA.), Luis Goddyn, (Simon Fraser University, Vancouver, Canada.), Bojan Mohar, (University of Ljublijana, Ljublijana, Slovenia.), Xuding Zhu, (National Sun Yat-Sen University, Kaohsiung, Taiwan.)
Suppose G=(V, E) is a graph and r >= 2 is a real number.
A proper r-coloring of G is a mapping
f: V --> [0, r) such that for every edges xy of G,
1 <= |f(x) - f(y)| <= r-1. The circular
chromatic number \chic(G) of G is the least
r for which G is r-colorable.
For an oriented graph G, a flow is a mapping
f: E --> R such that for each vertex v,
\Sigmae in E+(v)f(e) = \Sigmae in E-(v)f(e).
A proper r-flow is a flow f such that for each edge
e, 1 <= |f(e)| <= r-1. The
circular flow number \Phic(G) of a
undirected graph G is the least r for which
an orientation of G admits a proper r-flow.
It is not difficult to derive from the definition
that for any graph
|
\chi(G)-1 < \chic(G) <= \chi(G), |
|
|
\Phi(G)-1 < \Phic(G) <= \Phi(G). |
|
Moreover, circular coloring and flow are dual concepts in the sense that,
for a planar graph G and its dual G*,
This extends to regular matroids.
Here, we consider the relationship between the circular
chromatic number of a graph G on a surface \Sigma, and the circular
flow number of its surface dual G\Sigma*. The edge-width
of G on the surface \Sigma is the length of the shortest non-null
homotopic circuit. We prove the following theorem.
Suppose \Sigma is an orientable surface. For any
\epsilon > 0, there exists a constant c such that
if G is a graph embedded in \Sigma with edge-width
at least c then
|
\Phic(G\Sigma*) <= \chic(G) <= \Phic(G\Sigma*)+\epsilon. |
|
A related result holds for all surfaces.
Date received: April 19, 2001
Copyright © 2001 by the author(s).
The author(s) of this document and the organizers of the conference
have granted their consent to include this abstract in
Atlas Mathematical Conference Abstracts.
Document # cags-46.