167 citations · 303 across the 12 of their papers we have counts for
14 papers
Three-cuts are a charm: acyclicity in 3-connected cubic graphs
František Kardoš, Edita Máčajová, Jean Paul Zerafa
Let be a bridgeless cubic graph. In 2023, the three authors solved a conjecture (also known as the -Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchi…
Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
František Kardoš, Edita Máčajová, Jean Paul Zerafa
Let be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that admits a list of six perfect matchings such that each edge of belongs to exactly tw…
Strengthening a theorem of Meyniel
Quentin Deschamps, Carl Feghali, František Kardoš +2
For an integer and a graph , let be the graph that has vertex set all proper -colorings of , and an edge between two vertices and~ whe…
Subcubic planar graphs of girth 7 are class I
Sebastien Bonduelle, František Kardoš
We prove that planar graphs of maximum degree 3 and of girth at least 7 are 3-edge-colorable, extending the previous result for girth at least 8 by Kronk, Radlowski, and Franen fro…
On the 4-color theorem for signed graphs
František Kardoš, Jonathan Narboni
There are several ways to generalize graph coloring to signed graphs. Máčajová, Raspaud and Škoviera introduced one of them and conjectured that in this setting, for signed planar…
The structure of binary matroids with no induced claw or Fano plane restriction
Marthe Bonamy, Frantisek Kardos, Tom Kelly +2
An 'induced restriction' of a simple binary matroid is a restriction , where is a flat of . We consider the class of all simple binary matroids co…
First order convergence of matroids
Frantisek Kardos, Daniel Kral, Anita Liebenau +1
The model theory based notion of the first order convergence unifies the notions of the left-convergence for dense structures and the Benjamini-Schramm convergence for sparse struc…
Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
Frantisek Kardos, Daniel Kral, Jan Volec
We show that for every cubic graph G with sufficiently large girth there exists a probability distribution on edge-cuts of G such that each edge is in a randomly chosen cut with pr…
Minimum k-path vertex cover
Boštjan Brešar, František Kardoš, Ján Katrenič +1
A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ψ_k(G) the minimum cardinality of a…
Exponentially many perfect matchings in cubic graphs
Louis Esperet, Frantisek Kardos, Andrew King +2
We show that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. This confirms an old conjecture of Lovasz and Plummer. This version of the paper uses a…
Fractional colorings of cubic graphs with large girth
Frantisek Kardos, Daniel Kral, Jan Volec
We show that every (sub)cubic n-vertex graph with sufficiently large girth has fractional chromatic number at most 2.2978 which implies that it contains an independent set of size…
A superlinear bound on the number of perfect matchings in cubic bridgeless graphs
L. Esperet, F. Kardos, D. Kral'
Lovasz and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorh…
The last fraction of a fractional conjecture
Frantisek Kardos, Daniel Kral, Jean-Sebastien Sereni
Reed conjectured that for every and every integer , there exists such that the fractional total chromatic number of every graph with maximum degree and g…
Fullerene graphs have exponentially many perfect matchings
Frantisek Kardos, Daniel Král', Jozef Miskuf +1
A fullerene graph is a planar cubic 3-connected graph with only pentagonal and hexagonal faces. We show that fullerene graphs have exponentially many perfect matchings.