सार : Graphs associated with most real-life applications change with time. Few examples are road networks, social networks, and resource allocation graphs. The dynamic graph model allows changes to the input graph by supporting updates, the insertion of a new edge, or the deletion of an existing edge. A dynamic graph algorithm that supports both insertion or deletion is called a fully dynamic algorithm. If a dynamic graph algorithm supports only insertion, then it is called an incremental algorithm. A dynamic graph algorithm supporting only deletion is called a decremental algorithm. One immediate solution to any problem in the dynamic graph model is to run the best known static algorithm at the end of every update and recompute the solution from scratch. Therefore, a primary research goal in dynamic graph algorithms is to design efficient data structures to avoid recomputation at the end of every update. The time required to update such data structures must be significantly smaller than the best known static algorithms' running time. In this thesis, we consider the problem of dynamic coloring and dynamic matching.
The dynamic coloring problem has received significant attention in recent years. One research direction focuses on obtaining a trade-off between the number of colors used and the number of vertices getting recolored per update. The work of Barba et al. in WADS'17 and Solomon et al. in ESA'18 falls in this direction, and their algorithms run in exponential time. The other research direction focuses on obtaining efficient update time using $\Delta+1$ colors, where $\Delta$ is the maximum vertex degree. In SODA'18, Bhattacharya et al. presented a randomized $\Delta+1$-coloring algorithm that achieves $O(\log \Delta)$ amortized update time, and a deterministic $\Delta + o(\Delta)$-coloring algorithm that achieves $O(polylog \Delta)$ amortized update time.Recently in STACS'20, Henzinger et al. presented a randomized algorithm that uses $\Delta+1$ colors and achieves an update time of amortized $O(1)$. While the works of Bhattacharya et al. and Henzinger et al. achieve efficient update time; they do not address the number of recolorings per update. We bridge these two research directions by designing efficient update time algorithms with a constant number of recolorings per update. Suppose the color of a vertex is explicitly stored in a data structure and updated at the end of every update. In that case, we call such an algorithm as an explicit coloring algorithm. All the previous works on dynamic coloring use the explicit coloring approach. We introduce the notion of implicit coloring. In the implicit coloring approach, every vertex color is not maintained explicitly at the end of every update. However, the color information is correctly computed as and when required. We present a comprehensive set of results for implicit and explicit coloring of bipartite graphs. The dynamic coloring problem is not explicitly studied to interval graphs. However, the online coloring of interval graphs has been extensively studied, and there are optimal online algorithms. The online setting is similar to the incremental setting except that recoloring a previously colored interval is forbidden in the online setting. In contrast, an incremental algorithm is allowed to perform recoloring, but the update time should be as small as possible. We present efficient incremental and fully dynamic coloring algorithm for interval graphs that do not perform any recoloring. The problem of maintaining a maximal matching in the fully dynamic setting is very well studied. The state of the art result is a randomized algorithm due to Solomon in FOCS'16 that archives O(1) expected amortized update time, and a deterministic algorithm due to Neiman et al. in STOC'13 that achieves O(\sqrt{m}) worst case update time with $m$ being the number of edges in the current graph. We observe a characteristic property that is common to the Solomon algorithm and the Neiman et al. algorithm. We consider the class of algorithms without the characteristic property and prove lower bounds for such algorithms' update time. Maintaining a c-approximate maximum matching with c