4 papers
Saturation and semisaturation of oriented graphs
Vladimir Bošković, Balázs Keszegh
We consider a natural extension of the classical saturation problem to oriented graphs, defined as the minimum number of edges in an oriented graph on vertices that avoids…
Optimal Bounds on Spanning Tree Embeddings
Csongor Beke, Vladimir Bošković, Nina Kamčev +1
We prove that the number of labelled embeddings of any -vertex tree into an -vertex graph of maximum degree satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1…
Flip dynamics on perfect matchings beyond bipartite and planar graphs
Vladimir Bošković
We study the flip dynamics on perfect matchings of graphs, where a flip consists of replacing the edges of a perfect matching along an even cycle with the complementary alternating…
Saturation of Ordered Graphs
Vladimir Bošković, Balázs Keszegh
Recently, the saturation problem of - matrices gained a lot of attention. This problem can be regarded as a saturation problem of ordered bipartite graphs. Motivated by this,…