2 papers
math.CO2023
Reconstruction of graph colourings
Yury Demidovich, Yaroslav Panichkin, Maksim Zhukovskii
A -deck of a (coloured) graph is a multiset of its induced -vertex subgraphs. Given a graph , when is it possible to reconstruct with high probability a uniformly random c…
math.CO2021
Cycle saturation in random graphs
Yury Demidovich, Arkadiy Skorkin, Maksim Zhukovskii
For a fixed graph the minimum number of edges in an edge-maximal -free subgraph of is called the -saturation number. The asymptotics of the -saturation number of…