Source author record

Bernard Lidický

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Complexity Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

33works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Semi-Inducibility of some small graphs

Let $H$ be a fixed graph whose edges are colored red and blue and let $β\in [0,1]$ . Let $I(H, β)$ be the (asymptotically normalized) maximum number of copies of $H$ in a large red/blue edge-colored complete graph $G$ , where the density of red edges in $G$ is $β$ . This refines the problem of determining the semi-inducibility of $H$ , which is itself a generalization of the classical question of determining the inducibility of $H$ . The function $I(H, β)$ for $β\in [0,1]$ was not known for any graph $H$ on more than three vertices, except when $H$ is a monochromatic clique (Kruskal-Katona) or a monochromatic star (Reiher-Wagner). We obtain sharp results for some four and five vertex graphs, addressing several recent questions posed by various authors. We also obtain some general results for trees and stars. Many open problems remain.

preprint2022arXiv

On tripartite common graphs

A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdos, conjectured that every graph is common. The conjectures by Erdos and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenko's conjecture. Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle-trees, which generalises two theorems by Sidorenko and answers a question by Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle-tree such that the graph obtained by adding T as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most five vertices give a common graph.

preprint2021arXiv

Coloring count cones of planar graphs

For a plane near-triangulation $G$ with the outer face bounded by a cycle $C$ , let $n^\star_G$ denote the function that to each $4$ -coloring $ψ$ of $C$ assigns the number of ways $ψ$ extends to a $4$ -coloring of $G$ . The block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function $n^\star_G$ belongs to a certain cone in the space of all functions from $4$ -colorings of $C$ to real numbers. We investigate the properties of this cone for $|C|=5$ , formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture.

preprint2021arXiv

Maximizing five-cycles in $K_r$ -free graphs

The Erdős Pentagon problem asks to find an $n$ -vertex triangle-free graph that is maximizing the number of $5$ -cycles. The problem was solved using flag algebras by Grzesik and independently by Hatami, Hladký, Král', Norin, and Razborov. Recently, Palmer suggested the general problem of maximizing the number of $5$ -cycles in $K_{k+1}$ -free graphs. Using flag algebras, we show that every $K_{k+1}$ -free graph of order $n$ contains at most $\frac{1}{10k^4}(k^4 - 5k^3 + 10k^2 - 10k + 4)n^5 + o(n^5)$ copies of $C_5$ for any $k \geq 3$ , with the Turán graph begin the extremal graph for large enough $n$ .

preprint2021arXiv

Maximum Number of Almost Similar Triangles in the Plane

A triangle $T'$ is $\varepsilon$ -similar to another triangle $T$ if their angles pairwise differ by at most $\varepsilon$ . Given a triangle $T$ , $\varepsilon>0$ and $n\in\mathbb{N}$ , Bárány and Füredi asked to determine the maximum number of triangles $h(n,T,\varepsilon)$ being $\varepsilon$ -similar to $T$ in a planar point set of size $n$ . We show that for almost all triangles $T$ there exists $\varepsilon=\varepsilon(T)>0$ such that $h(n,T,\varepsilon)=n^3/24 (1+o(1))$ . Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof.

preprint2021arXiv

Solving Turán's Tetrahedron Problem for the $\ell_2$ -Norm

Turán's famous tetrahedron problem is to compute the Turán density of the tetrahedron $K_4^3$ . This is equivalent to determining the maximum $\ell_1$ -norm of the codegree vector of a $K_4^3$ -free $n$ -vertex $3$ -uniform hypergraph. We introduce a new way for measuring extremality of hypergraphs and determine asymptotically the extremal function of the tetrahedron in our notion. The codegree squared sum, $\text{co}_2(G)$ , of a $3$ -uniform hypergraph $G$ is the sum of codegrees squared $d(x,y)^2$ over all pairs of vertices $xy$ , or in other words, the square of the $\ell_2$ -norm of the codegree vector of the pairs of vertices. We define $\text{exco}_2(n,H)$ to be the maximum $\text{co}_2(G)$ over all $H$ -free $n$ -vertex $3$ -uniform hypergraphs $G$ . We use flag algebra computations to determine asymptotically the codegree squared extremal number for $K_4^3$ and $K_5^3$ and additionally prove stability results. In particular, we prove that the extremal $K_4^3$ -free hypergraphs in $\ell_2$ -norm have approximately the same structure as one of the conjectured extremal hypergraphs for Turán's conjecture. Further, we prove several general properties about $\text{exco}_2(n,H)$ including the existence of a scaled limit, blow-up invariance and a supersaturation result.

preprint2020arXiv

Hadamard diagonalizable graphs of order at most 36

If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $\pm1$ , then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable. In this article, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$ , $K_{n/2,n/2}$ , $2K_{n/2}$ , and $nK_1$ , and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to order 36. Note that it is not even known how many Hadamard matrices there are of order 36.

preprint2020arXiv

Inducibility of directed paths

A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.

preprint2020arXiv

Semidefinite Programming and Ramsey Numbers

Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra method was developed to find asymptotic results for very large graphs, so it seems that the method is not suitable for finding small Ramsey numbers. But this intuition is wrong, and we will develop a technique to do just that in this paper. We find new upper bounds for many small graph and hypergraph Ramsey numbers. As a result, we prove the exact values $R(K_4^-,K_4^-,K_4^-)=28$ , $R(K_8,C_5)= 29$ , $R(K_9,C_6)= 41$ , $R(Q_3,Q_3)=13$ , $R(K_{3,5},K_{1,6})=17$ , $R(C_3, C_5, C_5)= 17$ , and $R(K_4^-,K_5^-;3)= 12$ . We hope that this technique will be adapted to address other questions for smaller graphs with the flag algebra method.

preprint2019arXiv

Making $K_{r+1}$ -Free Graphs $r$ -partite

The Erdős-Simonovits stability theorem states that for all ε>0 there exists α>0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - αn^2, then one can remove εn^2 edges from G to obtain an r-partite graph. Füredi gave a short proof that one can choose α=ε. We give a bound for the relationship of αand \varepsilon which is asymptotically sharp as ε\to 0.

preprint2019arXiv

Minimizing the number of 5-cycles in graphs with given edge-density

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle $C_5$ . We show that every graph of order $n$ and size $\left( 1-\frac{1}{k}\right)\binom{n}{2}$ , where $k\ge 3$ is an integer, contains at least $\left( \frac{1}{10} -\frac{1}{2k} + \frac{1}{k^2} - \frac{1}{k^3} + \frac{2}{5 k^4} \right)n^5 +o(n^5)$ copies of $C_5$ . This bound is optimal, since a matching upper bound is given by the balanced complete $k$ -partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.

preprint2019arXiv

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~ $G$ begin in one of two states, "dormant" or "active". Given a fixed integer $r$ , a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$ , we say that $G$ $r$ -percolates (from $A$ ) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$ -percolates from $A$ . Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$ . In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $σ_2(G)\ge n-2$ , then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chvátal-type degree condition: If $G$ is a graph with degree sequence $d_1\le d_2\le\dots\le d_n$ such that $d_i \geq i+1$ or $d_{n-i} \geq n-i-1$ for all $1 \leq i < \frac{n}{2}$ , then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. Combin.]

preprint2018arXiv

Closing in on Hill's conjecture

Borrowing László Székely's lively expression, we show that Hill's conjecture is "asymptotically at least 98.5% true". This long-standing conjecture states that the crossing number cr( $K_n$ ) of the complete graph $K_n$ is $H(n) := \frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ , for all $n\ge 3$ . This has been verified only for $n\le 12$ . Using flag algebras, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that for every sufficiently large $n$ , cr $(K_n) > 0.905\, H(n)$ . Also using flag algebras, we prove that asymptotically cr $(K_n)$ is at least $0.985\, H(n)$ . We also show that the spherical geodesic crossing number of $K_n$ is asymptotically at least $0.996\, H(n)$ .

preprint2018arXiv

Facial unique-maximum colorings of plane graphs with restriction on big vertices

A facial unique-maximum coloring of a plane graph is a proper coloring of the vertices using positive integers such that each face has a unique vertex that receives the maximum color in that face. Fabrici and Göring (2016) proposed a strengthening of the Four Color Theorem conjecturing that all plane graphs have a facial unique-maximum coloring using four colors. This conjecture has been disproven for general plane graphs and it was shown that five colors suffice. In this paper we show that plane graphs, where vertices of degree at least four induce a star forest, are facially unique-maximum 4-colorable. This improves a previous result for subcubic plane graphs by Andova, Lidický, Lužar, and Škrekovski (2018). We conclude the paper by proposing some problems.

preprint2018arXiv

Polychromatic Colorings on the Integers

We show that for any set $S\subseteq \mathbb{Z}$ , $|S|=4$ there exists a 3-coloring of $\mathbb{Z}$ in which every translate of $S$ receives all three colors. This implies that $S$ has a codensity of at most $1/3$ , proving a conjecture of Newman [D. J. Newman, Complements of finite sets of integers, Michigan Math. J. 14 (1967) 481--486]. We also consider related questions in $\mathbb{Z}^d$ , $d\geq 2$ .

preprint2017arXiv

Pentagons in triangle-free graphs

For all $n\ge 9$ , we show that the only triangle-free graphs on $n$ vertices maximizing the number $5$ -cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by Erdős, and extends results by Grzesik and Hatami, Hladký, Král', Norin and Razborov, where they independently showed this same result for large $n$ and for all $n$ divisible by $5$ .

preprint2014arXiv

4-critical graphs on surfaces without contractible (<=4)-cycles

We show that if G is a 4-critical graph embedded in a fixed surface $Σ$ so that every contractible cycle has length at least 5, then G can be expressed as $G=G'\cup G_1\cup G_2\cup ... \cup G_k$ , where $|V(G')|$ and $k$ are bounded by a constant (depending linearly on the genus of $Σ$ ) and $G_1\ldots,G_k$ are graphs (of unbounded size) whose structure we describe exactly. The proof is computer-assisted - we use computer to enumerate all plane 4-critical graphs of girth 5 with a precolored cycle of length at most 16, that are used in the basic case of the inductive proof of the statement.

preprint2014arXiv

Crossing numbers of complete tripartite and balanced complete multipartite graphs

The crossing number cr(G) of a graph G is the minimum number of crossings in a nondegenerate planar drawing of G. The rectilinear crossing number cr'(G) of G is the minimum number of crossings in a rectilinear nondegenerate planar drawing (with edges as straight line segments) of G. Zarankiewicz proved in 1952 that cr'(K_{n_1,n_2})\le Z(n_1,n_2):= n_1/2*(n_1-1)/2*n_2/2*(n_2-1)/2. We define an analogous bound A(n_1,n_2,n_3) for the complete tripartite graph K_{n_1,n_2,n_3}, and prove that cr'(K_{n_1,n_2,n_3})\le A({n_1,n_2,n_3}). We also show that for n large enough, 0.973 A(n,n,n) \le cr'(K_{n,n,n}) and 0.666 A(n,n,n)\le cr(K_{n,n,n}), with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r-partite graph. Richter and Thomassen proved in 1997 that the limit as n\to\infty of cr(K_{n,n}) over the maximum number of crossings in a drawing of K_{n,n} exists and is at most 1/4. We define z(r)=3(r^2-r)/8(r^2+r-3) and show that for a fixed r and the balanced complete r-partite graph, z(r) is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.

preprint2014arXiv

Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle

Let $C(n)$ denote the maximum number of induced copies of 5-cycles in graphs on $n$ vertices. For $n$ large enough, we show that $C(n)=a\cdot b\cdot c \cdot d \cdot e + C(a)+C(b)+C(c)+C(d)+C(e)$ , where $a+b+c+d+e = n$ and $a,b,c,d,e$ are as equal as possible. Moreover, if $n$ is a power of 5, we show that the unique graph on $n$ vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle.

preprint2014arXiv

Minimum number of monotone subsequences of length 4 in permutations

We show that for every sufficiently large $n$ , the number of monotone subsequences of length four in a permutation on $n$ points is at least $\binom{\lfloor n/3 \rfloor}{4} + \binom{\lfloor(n+1)/3\rfloor}{4} + \binom{\lfloor (n+2)/3\rfloor}{4}$ . Furthermore, we characterize all permutations on $[n]$ that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colorings of complete graphs with two colors, where the number of monochromatic $K_4$ 's is minimized. We show that all the extremal colorings must contain monochromatic $K_4$ 's only in one of the two colors. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.

preprint2014arXiv

On the Tree Search Problem with Non-uniform Costs

Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indexes, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query $e$ returns the component of $T-e$ containing the vertex sought for, while incurring some known cost $c(e)$ . The Tree Search Problem with Non-Uniform Cost is: given a tree $T$ where each edge has an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case. Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input tree of degree 3 or diameter 6. The best known approximation guarantee is the $O(\log n/\log \log \log n)$ -approximation algorithm of [Cicalese et al. TCS 2012]. We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an $O(\frac{\log n}{\log \log n})$ -approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-complete even when the input tree is a spider, i.e., at most one vertex has degree larger than 2.

preprint2013arXiv

3-coloring triangle-free planar graphs with a precolored 8-cycle

Let G be a planar triangle-free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3-coloring of C does not extend to a proper 3-coloring of the whole graph.

preprint2013arXiv

On Choosability with Separation of Planar Graphs with Forbidden Cycles

We study choosability with separation which is a constrained version of list coloring of graphs. A (k,d)-list assignment L on a graph G is a function that assigns to each vertex v a list L(v) of at least k colors and for any adjacent pair xy, the lists L(x) and L(y) share at most d colors. A graph G is (k,d)-choosable if there exists an L-coloring of G for every (k,d)-list assignment L. This concept is also known as choosability with separation. We prove that planar graphs without 4-cycles are (3,1)-choosable and that planar graphs without 5-cycles and 6-cycles are (3,1)-choosable. In addition, we give an alternative and slightly stronger proof that triangle-free planar graphs are $(3,1)$ -choosable.

preprint2013arXiv

On choosability with separation of planar graphs with lists of different sizes

A (k,d)-list assignment L of a graph G is a mapping that assigns to each vertex v a list L(v) of at least k colors and for any adjacent pair xy, the lists L(x) and L(y) share at most d colors. A graph G is (k,d)-choosable if there exists an L-coloring of G for every (k,d)-list assignment L. This concept is also known as choosability with separation. It is known that planar graphs are (4,1)-choosable but it is not known if planar graphs are (3,1)-choosable. We strengthen the result that planar graphs are (4,1)-choosable by allowing an independent set of vertices to have lists of size 3 instead of 4.

preprint2013arXiv

Peeling the Grid

Consider the set of points formed by the integer $n \times n$ grid, and the process that in each iteration removes from the point set the vertices of its convex-hull. Here, we prove that the number of iterations of this process is O(n^{4/3}); that is, the number of convex layers of the $n\times n$ grid is Θ(n^{4/3}).

preprint2013arXiv

Planar 4-critical graphs with four triangles

By the Grunbaum-Aksenov Theorem (extending Grotzsch's Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdos from 1990.

preprint2012arXiv

Finding vertex-surjective graph homomorphisms

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes G and H, respectively. We determine to what extent a certain choice of G and H influences its computational complexity. We observe that the problem is polynomial-time solvable if H is the class of paths, whereas it is NP-complete if G is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if G is the class of trees and H is the class of trees with at most k leaves, or if G and H are equal to the class of graphs with vertex cover number at most k.

preprint2012arXiv

On the Turan number of forests

The Turan number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. We determine the Turan number and find the unique extremal graph for forests consisting of paths when n is sufficiently large. This generalizes a result of Bushaw and Kettle [ Combinatorics, Probability and Computing 20:837--853, 2011]. We also determine the Turan number and extremal graphs for forests consisting of stars of arbitrary order.

preprint2012arXiv

Short proofs of coloring theorems on planar graphs

A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grötzsch Theorem that every planar triangle-free graph is 3-colorable. In this paper we use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Grünbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most four is 3-colorable.

preprint2012arXiv

Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

In this paper we modify slightly Razborov's flag algebra machinery to be suitable for the hypercube. We use this modified method to show that the maximum number of edges of a 4-cycle-free subgraph of the n-dimensional hypercube is at most 0.6068 times the number of its edges. We also improve the upper bound on the number of edges for 6-cycle-free subgraphs of the n-dimensional hypercube from the square root of 2 - 1 to 0.3755 times the number of its edges. Additionally, we show that if the n-dimensional hypercube is considered as a poset, then the maximum vertex density of three middle layers in an induced subgraph without 4-cycles is at most 2.15121 times n choose n/2.

preprint2011arXiv

Packing Chromatic Number of Distance Graphs

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that vertices of $G$ can be partitioned into disjoint classes $X_1, ..., X_k$ where vertices in $X_i$ have pairwise distance greater than $i$ . We study the packing chromatic number of infinite distance graphs $G(Z, D)$ , i.e. graphs with the set $Z$ of integers as vertex set and in which two distinct vertices $i, j \in Z$ are adjacent if and only if $|i - j| \in D$ . In this paper we focus on distance graphs with $D = \{1, t\}$ . We improve some results of Togni who initiated the study. It is shown that $χ_ρ(G(Z, D)) \leq 35$ for sufficiently large odd $t$ and $χ_ρ(G(Z, D)) \leq 56$ for sufficiently large even $t$ . We also give a lower bound 12 for $t \geq 9$ and tighten several gaps for $χ_ρ(G(Z, D))$ with small $t$ .

preprint2010arXiv

The packing chromatic number of the square lattice is at least 12

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set $V(G)$ can be partitioned into disjoint classes $X_1, ..., X_k$ , where vertices in $X_i$ have pairwise distance greater than $i$ . For the 2-dimensional square lattice $\mathbb{Z}^2$ it is proved that $χ_ρ(\mathbb{Z}^2) \geq 12$ , which improves the previously known lower bound 10.

preprint2010arXiv

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum number of distinct edge-slopes in such a drawing of a planar graph with maximum degree $Δ$ . We show that the planar slope number of every planar partial 3-tree and also every plane partial 3-tree is at most $O(Δ^5)$ . In particular, we answer the question of Dujmović et al. [Computational Geometry 38 (3), pp. 194--212 (2007)] whether there is a function $f$ such that plane maximal outerplanar graphs can be drawn using at most $f(Δ)$ slopes.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Bernard Lidický

Research overview

Is this your work?

33 publications

Semi-Inducibility of some small graphs

On tripartite common graphs

Coloring count cones of planar graphs

Maximizing five-cycles in $K_r$ -free graphs

Maximum Number of Almost Similar Triangles in the Plane

Solving Turán's Tetrahedron Problem for the $\ell_2$ -Norm

Hadamard diagonalizable graphs of order at most 36

Inducibility of directed paths

Semidefinite Programming and Ramsey Numbers

Making $K_{r+1}$ -Free Graphs $r$ -partite

Minimizing the number of 5-cycles in graphs with given edge-density

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Closing in on Hill's conjecture

Facial unique-maximum colorings of plane graphs with restriction on big vertices

Polychromatic Colorings on the Integers

Pentagons in triangle-free graphs

4-critical graphs on surfaces without contractible (<=4)-cycles

Crossing numbers of complete tripartite and balanced complete multipartite graphs

Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle

Minimum number of monotone subsequences of length 4 in permutations

On the Tree Search Problem with Non-uniform Costs

3-coloring triangle-free planar graphs with a precolored 8-cycle

On Choosability with Separation of Planar Graphs with Forbidden Cycles

On choosability with separation of planar graphs with lists of different sizes

Peeling the Grid

Planar 4-critical graphs with four triangles

Finding vertex-surjective graph homomorphisms

On the Turan number of forests

Short proofs of coloring theorems on planar graphs

Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

Packing Chromatic Number of Distance Graphs

The packing chromatic number of the square lattice is at least 12

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

See the researcher in context

Building this map preview

Bernard Lidický

Research overview

Is this your work?

33 publications

Semi-Inducibility of some small graphs

On tripartite common graphs

Coloring count cones of planar graphs

Maximizing five-cycles in KrK_rKr​-free graphs

Maximum Number of Almost Similar Triangles in the Plane

Solving Turán's Tetrahedron Problem for the ℓ2\ell_2ℓ2​-Norm

Hadamard diagonalizable graphs of order at most 36

Inducibility of directed paths

Semidefinite Programming and Ramsey Numbers

Making Kr+1K_{r+1}Kr+1​-Free Graphs rrr-partite

Minimizing the number of 5-cycles in graphs with given edge-density

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Closing in on Hill's conjecture

Facial unique-maximum colorings of plane graphs with restriction on big vertices

Polychromatic Colorings on the Integers

Pentagons in triangle-free graphs

4-critical graphs on surfaces without contractible (<=4)-cycles

Crossing numbers of complete tripartite and balanced complete multipartite graphs

Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle

Minimum number of monotone subsequences of length 4 in permutations

On the Tree Search Problem with Non-uniform Costs

3-coloring triangle-free planar graphs with a precolored 8-cycle

On Choosability with Separation of Planar Graphs with Forbidden Cycles

On choosability with separation of planar graphs with lists of different sizes

Peeling the Grid

Planar 4-critical graphs with four triangles

Finding vertex-surjective graph homomorphisms

On the Turan number of forests

Short proofs of coloring theorems on planar graphs

Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

Packing Chromatic Number of Distance Graphs

The packing chromatic number of the square lattice is at least 12

The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree

See the researcher in context

Building this map preview

Maximizing five-cycles in $K_r$ -free graphs

Solving Turán's Tetrahedron Problem for the $\ell_2$ -Norm

Making $K_{r+1}$ -Free Graphs $r$ -partite