A fully dynamic algorithm for maintaining maximal matching problem maintains a maximal match-
ing under insertion and deletion of edges, and also reports the size of the matching in constant time.
We consider two sub-classes of fully dynamic maximal matching algorithm, which we define as lazy
algorithms and eager algorithms. We prove a conditional lower bound which is sub-linear in the
number of edges for the update time of lazy algorithms and eager algorithms. Our result is condi-
tioned on the well known conjecture about the hardness of triangle detection in a graph.
Dynamic coloring problem has gained significant attention recently and focus has largely been
on developing algorithms with efficient update time using ∆ + 1 or more colors, where ∆ is the
maximum degree of a vertex in the underlying graph. While the recent works for dynamic coloring
are very efficient in terms of update time, they do not address the number of recolorings per update.
We bridge this gap by providing efficient update time deterministic algorithm with constant number
of recolorings. We study coloring for bipartite graphs which can be optimally performed in the static
setting. We show that even in the incremental setting there is a bad update sequence which forces
update time to be amortized Ω(log n) and worst case Ω(n). To circumvent this lower bound we
propose two approaches: using more than two colors and implicit coloring. If the color of vertex is
explicitly stored in a data structure and updated at the end of every update then we call such an
algorithm as explicit coloring algorithm. All prior work on dynamic coloring uses explicit coloring
algorithm. We show that using implicit coloring we can obtain near constant update time and
query time for incremental coloring of bipartite graph. In the fully dynamic setting for bipartite
graphs, we present a lower bound for any 2-coloring algorithm using the well known cell-probe
model. Our result shows that at least one of update time, query time or number of recolorings
is Ω(log n). We present an implicit 2-coloring fully dynamic algorithm for bipartite graphs with
amortized O(log^2(n)) update time, amortized O(log n) query time, and at most one recoloring