|
10/20, 10/27, Sriram Penumatcha, Department of Mathematics and Statistics,
Total Coloring of Graphs
Abstract:
A total coloring of graph G is an assignment of
colors to its vertices and edges so that no two adjacent
vertices have the same color, no two adjacent edges have
the same color and no edge has the same color as one of
its end points. We discuss algorithm for Total coloring
using delta+poly(log(delta)) colors.
This is from the paper by Hugh Hind, Michael Molloy, Bruce Reed.
|
|
11/10,
Melih Onus, Department of CSE, Distributed Coloring with $\tilde{O}(\sqrt{\log n})$ Bits
Abstract:
We consider the well-known vertex coloring problem: given a graph G, find a
coloring of the vertices so that no two neighbors in G have the same color.
It is trivial to see that every graph of maximum degree $\Delta$ can be colored
with $\Delta+1$ colors, and distributed algorithms that find a
$\Delta+1$-coloring in a logarithmic number of communication rounds, with high
probability, are known since more than a decade. This is in general best
possible if only a constant number of bits can be sent along every edge in each
round. In fact, we show that for the $n$-node cycle the bit complexity of
the coloring problem is $\Omega(\log n)$, or more precisely, if only one bit
can be sent along each edge in a round, then every distributed coloring
algorithm (i.e., algorithms in which every node has the same initial state and
initially only knows its own edges) needs at least $\Omega(\log n)$ rounds, on
expectation, to color the cycle, for any finite number of colors. But
what if the edges have orientations, i.e., the endpoints of an edge agree on
its orientation (while bits may still flow in both directions)? Edge
orientations naturally occur in dynamic networks where new nodes establish
connections to old nodes. Does this allow one to provide faster coloring
algorithms?
Interestingly, for the cycle in which all edges have the same orientation, we
show that a simple randomized algorithm can achieve a 3-coloring with only
O(\sqrt{\log n}) rounds of bit transmissions, with high probability (w.h.p.).
This result is tight because we also show that the bit complexity of coloring
an oriented cycle is $\Omega(\sqrt{\log n})$, no matter how many colors are
allowed. The 3-coloring algorithm can be easily extended to provide a
$\Delta+1$-coloring for all graphs of maximum degree $\Delta$ in $O(\sqrt{\log
n})$ rounds of bit transmissions, w.h.p., if $\Delta$ is a constant, the edges
are oriented, and the graph does not contain an oriented cycle of length less
than $\sqrt{\log n}$. Using more complex algorithms, we show how to obtain an
$O(\Delta)$-coloring for arbitrary graphs of maximum degree $\Delta$ using
essentially $\tilde{O}(\log \Delta + \sqrt{\log n})$ rounds of bit
transmissions.
|
|
11/17,
William Cushing, ASU, Cutting and Pasting Trees
Efficiently
Abstract:
In this talk, I will present a paper by A. El Sahili, "Trees in Tournaments" ,JCTB, 92 (2004).
The paper establishes the best known upper bound on the size of a
tournament (f(n)) in order to guarantee the existence of every tree on
n vertices as an isomorphic subgraph of the tournament. Sumner
conjectured that f(n) = 2(n-1). Since that time a series of papers
has been published giving progressively better bounds, using a variety
of techniques:
Wormald:
f(n) <= n lg (2n/e)
Reid and Wormald:
f(n) = { 2(n-1) if T is near-regular
? otherwise
H:aggkvist and Thomason:
f(n) <= 12n
also
f(n) <= (4+o(1)) n
Havet :
f(n) <= 7.6n
Havet and Thomasse':
f(n) <= (7n-5)/2 (technical proof) <= 4n - 6 (simple proof)
also
f(n) = { 2(n-1) if A is a branching
? otherwise
Sahili:
f(n) <= 3(n-1)
f(n) = { 2(n-1) if A is "path-like"
? otherwise
All of these papers typically introduce a different notion of a
"simple" piece of a tree. For example, the first technique performs
induction on the tree (A) by removing a single leaf. Later papers
remove larger portions of the tree, or partition the tournament in a
sneakier fashion, or both. The technique by Sahili removes branchings
(arborescences) and structures the tournament using median orders.
Another common theme is all of these papers is to present Corollaries
for special cases which meet Sumner's Conjecture; for example, in
Sahili's paper, he shows that "path-like" trees meet the bound.
For the talk, I'd like to present Sahili's argument in detail, as well
as relate the technique to the history of techniques that have
preceded.
|
|
|
