Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Dynamic Algorithms for Graph Coloring   We design fast dynamic algorithms for proper vertex and edge colorings in a
graph undergoing edge insertions and deletions. In the static setting, there
are simple linear time algorithms for $(\Delta+1)$- vertex coloring and
$(2\Delta-1)$-edge coloring in a graph with maximum degree $\Delta$. It is
natural to ask if we can efficiently maintain such colorings in the dynamic
setting as well. We get the following three results. (1) We present a
randomized algorithm which maintains a $(\Delta+1)$-vertex coloring with
$O(\log \Delta)$ expected amortized update time. (2) We present a deterministic
algorithm which maintains a $(1+o(1))\Delta$-vertex coloring with
$O(\text{poly} \log \Delta)$ amortized update time. (3) We present a simple,
deterministic algorithm which maintains a $(2\Delta-1)$-edge coloring with
$O(\log \Delta)$ worst-case update time. This improves the recent
$O(\Delta)$-edge coloring algorithm with $\tilde{O}(\sqrt{\Delta})$ worst-case
update time by Barenboim and Maimon.

11
The categories of this paper are: hep-lat
21
The categories of this paper are: adap-org
6
The categories of this paper are: astro-ph
18
The categories of this paper are: econ
22
The categories of this paper are: chao-dyn
0
The categories of this paper are: hep-ph
26
The categories of this paper are: bayes-an
3
The categories of this paper are: physics
5
The categories of this paper are: gr-qc
10
The categories of this paper are: q-bio
19
The categories of this paper are: eess
9
The categories of this paper are: nlin
12
The categories of this paper are: nucl-th
25
The categories of this paper are: patt-sol
16
The categories of this paper are: stat
35
The categories of this paper are: mtrl-th