22 citations · 31 across the 7 of their papers we have counts for
8 papers
The complexity of decomposing a graph into a matching and a bounded linear forest
Agnijo Banerjee, João Pedro Marciano, Adva Mond +2
Deciding whether a graph can be edge-decomposed into a matching and a -bounded linear forest was recently shown by Campbell, H{ö}rsch and Moore to be NP-complete for every $k \g…
Bounds for the Competition-Independence game on trees
Jan Petr, Julien Portier
In this paper we prove that Sweller has a strategy so that the Sweller-Start Competition-Independence game lasts at least moves for every tree. Moreover, we show that t…
On the number of minimum dominating sets and total dominating sets in forests
Jan Petr, Julien Portier, Leo Versteegen
We show that the maximum number of minimum dominating sets of a forest with domination number is at most and construct for each a tree with domination number $…
A note on Cops and Robbers, independence number, domination number and diameter
Jan Petr, Julien Portier, Leo Versteegen
We study relations between diameter , domination number , independence number and cop number of a connected graph , showing (i.) $c(G) \leq α(G)-\lfloo…
The odd chromatic number of a planar graph is at most 8
Jan Petr, Julien Portier
Petruševski and Škrekovski \cite{odd9} recently introduced the notion of an odd colouring of a graph: a proper vertex colouring of a graph is said to be \emph{odd} if for each…
A faster algorithm for Cops and Robbers
Jan Petr, Julien Portier, Leo Versteegen
We present an algorithm of time complexity deciding whether a graph on vertices is -copwin. The fastest algorithm thus far had time complexity $O(n^{2k+2})…
A new lower bound on the pebbling number of the grid
Jan Petr, Julien Portier, Szymon Stolarczyk
A pebbling move on a graph consists of removing pebbles from a vertex and adding pebble to one of the neighbouring vertices. A vertex is called reachable if we can put …
Slowdown for the geodesic-biased random walk
Mikhail Beliayeu, Petr Chmel, Bhargav Narayanan +1
Given a connected graph with some subset of its vertices excited and a fixed target vertex, in the geodesic-biased random walk on , a random walker moves as follows: from an…