Incremental DFS Algorithms : A Theoretical and Experimental Study by Surender Baswana, Ayush Goel, and Shahbaz Khan.
Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter by Krishnendu Chatterjee, Wolfgang Dvorak, Monika Henzinger, and Veronika Loitzenbauer
Dynamic Algorithms for Graph Coloring by Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai
Estimating Graph Parameters from Random Order Streams by Pan Peng and Christian Sohler