4 citations · 9 across the 8 of their papers we have counts for
9 papers
Bipartite cuts in Ramsey-Turán style
József Balogh, Ce Chen, Bernard Lidický
We prove that every -free -vertex graph with sublinear independence number can be made bipartite by removing at most edges, where the constant is be…
Embedded graph 3-coloring and flows
Caroline Bang, Zdeněk Dvořák, Emily Heath +1
A graph drawn in a surface is a near-quadrangulation if the sum of the lengths of the faces different from 4-faces is bounded by a fixed constant. We leverage duality between color…
Weighted Turán theorems with applications to Ramsey-Turán type of problems
József Balogh, Domagoj Bradač, Bernard Lidický
We study extensions of Turán Theorem in edge-weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique…
Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4
Eun-Kyung Cho, Ilkyoo Choi, Bernard Lidický
The famous Wegner's Planar Graph Conjecture asserts tight upper bounds on the chromatic number of the square of a planar graph , depending on the maximum degree of…
Nearly all -SAT functions are unate
József Balogh, Dingding Dong, Bernard Lidický +2
We prove that fraction of all -SAT functions on Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer …
11/4-colorability of subcubic triangle-free graphs
Zdeněk Dvořák, Bernard Lidický, Luke Postle
We prove that up to two exceptions, every connected subcubic triangle-free graph has fractional chromatic number at most 11/4. This is tight unless further exceptional graphs are e…
Shortened universal cycles for permutations
Rachel Kirsch, Bernard Lidický, Clare Sibley +1
Kitaev, Potapov, and Vajnovszki [On shortening u-cycles and u-words for permutations, Discrete Appl. Math, 2019] described how to shorten universal words for permutations, to lengt…
The Spectrum of Triangle-free Graphs
József Balogh, Felix Christian Clemen, Bernard Lidický +2
Denote by the smallest eigenvalue of the signless Laplacian matrix of an -vertex graph . Brandt conjectured in 1997 that for regular triangle-free graphs $q_n(G) \le…
10 Problems for Partitions of Triangle-free Graphs
József Balogh, Felix Christian Clemen, Bernard Lidický
We will state 10 problems, and solve some of them, for partitions in triangle-free graphs related to Erdős' Sparse Half Conjecture. Among others we prove the following variant of i…