58 citations · 549 across the 45 of their papers we have counts for
6 papers · 1 filter
Independent sets near the lower bound in bounded degree graphs
Zdenek Dvorak, Bernard Lidicky
By Brook's Theorem, every n-vertex graph of maximum degree at most Delta >= 3 and clique number at most Delta is Delta-colorable, and thus it has an independent set of size at leas…
Irreversible 2-conversion set in graphs of bounded degree
Jan Kynčl, Bernard Lidický, Tomáš Vyskočil
An irreversible -threshold process (also a -neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at le…
Peeling the Grid
Sariel Har-Peled, Bernard Lidický
Consider the set of points formed by the integer grid, and the process that in each iteration removes from the point set the vertices of its convex-hull. Here, we prov…
Packing Chromatic Number of Distance Graphs
Jan Ekstein, Přemysl Holub, Bernard Lidický
The packing chromatic number of a graph is the smallest integer such that vertices of can be partitioned into disjoint classes where vertices i…
The packing chromatic number of the square lattice is at least 12
Jan Ekstein, Jiří Fiala, Přemysl Holub +1
The packing chromatic number of a graph is the smallest integer such that the vertex set can be partitioned into disjoint classes , where ver…
The k-in-a-path problem for claw-free graphs
Jiri Fiala, Marcin Kaminski, Bernard Lidicky +1
Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial tim…