4 citations · 9 across the 8 of their papers we have counts for
6 papers · 1 filter
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…