František Kardoš
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
František Kardoš has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Edita Máčajová
Comenius University, Slovakia
2 shared publications - Jean Paul Zerafa
University of Malta, Malta
2 shared publications - Borut Lužar
Faculty of Information Studies, Novo mesto, Slovenia
1 shared publication - Daniel W. Cranston
Department of Mathematics William & Mary Williamsburg VA USA
1 shared publication - Jonathan Narboni
Université de Bordeaux CNRS LaBRI F-33400 Talence France
1 shared publication Martina Mockovčiaková
Faculty of Applied Sciences, European Centre of Excellence NTIS University of West Bohemia Pilsen Czech Republic
1 shared publication
Latest Publications
- Open Access
Disjoint Correspondence Colorings for $K_5$-Minor-free Graphs
Thomassen famously proved that every planar graph is 5-choosable. We explore variants of this result, focusing on finding disjoint correspondence colorings, in the more general class of $K_5$-minor-free graphs. Correspondence colorings generalize list colorings as follows. Given a graph $G$ and a positive integer $t$, a correspondence $t$-cover $\textbf{M}$ assigns to each $v\in V(G)$ a set of allowable colors $\{1_v,\ldots,t_v\}$ and to each edge $vw\in E(G)$ a matching between $\{1_v,\ldots,t_v\}$ and $\{1_w,\ldots,t_w\}$. An $\textbf{M}$-coloring $\varphi$ picks for each vertex $v$ a color $\varphi(v)$ (from the set $\{1_v,\ldots,t_v\}$) such that for each edge $vw\in E(G)$ the colors $\varphi(v),\varphi(w)$ are not matched to each other. Two $\textbf{M}$-colorings $\varphi_1,\varphi_2$ of $G$ are called disjoint if $\varphi_1(v)\ne\varphi_2(v)$ for all $v\in V(G)$. For every $K_5$-minor-free graph $G$ and every correspondence 6-cover $\textbf{M}$ of $G$, we construct 3 pairwise disjoint $\textbf{M}$-colorings $\varphi_1,\varphi_2,\varphi_3$. In contrast, we provide examples of $K_5$-minor-free graphs and correspondence 5-covers $\textbf{M}$ that do not admit 3 disjoint $\textbf{M}$-colorings.Open AccessDisjoint Correspondence Colorings for $K_5$-Minor-free Graphs
Thomassen famously proved that every planar graph is 5-choosable. We explore variants of this result, focusing on finding disjoint correspondence colorings, in the more general class of $K_5$-minor-free graphs. Correspondence colorings generalize list colorings as follows. Given a graph $G$ and a positive integer $t$, a correspondence $t$-cover $\textbf{M}$ assigns to each $v\in V(G)$ a set of allowable colors $\{1_v,\ldots,t_v\}$ and to each edge $vw\in E(G)$ a matching between $\{1_v,\ldots,t_v\}$ and $\{1_w,\ldots,t_w\}$. An $\textbf{M}$-coloring $\varphi$ picks for each vertex $v$ a color $\varphi(v)$ (from the set $\{1_v,\ldots,t_v\}$) such that for each edge $vw\in E(G)$ the colors $\varphi(v),\varphi(w)$ are not matched to each other. Two $\textbf{M}$-colorings $\varphi_1,\varphi_2$ of $G$ are called disjoint if $\varphi_1(v)\ne\varphi_2(v)$ for all $v\in V(G)$. For every $K_5$-minor-free graph $G$ and every correspondence 6-cover $\textbf{M}$ of $G$, we construct 3 pairwise disjoint $\textbf{M}$-colorings $\varphi_1,\varphi_2,\varphi_3$. In contrast, we provide examples of $K_5$-minor-free graphs and correspondence 5-covers $\textbf{M}$ that do not admit 3 disjoint $\textbf{M}$-colorings. - Open Access
- 12 February 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (1) , 1-21
Three-Cuts are a Charm: Acyclicity in 3-Connected Cubic Graphs
Let G be a bridgeless cubic graph. In 2023, the three authors solved a conjecture (also known as the $$S_4$$ -Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchings of G such that the complement of their union is a bipartite subgraph of G. They actually show that given any $$1^+$$ -factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G, there exists a perfect matching M of G containing e such that $$G\setminus (F\cup M)$$ is bipartite. This is a step closer to comprehend better the Fan–Raspaud Conjecture and eventually the Berge–Fulkerson Conjecture. The $$S_4$$ -Conjecture, now a theorem, is also the weakest assertion in a series of three conjectures made by Mazzuoccolo in 2013, with the next stronger statement being: there exist two perfect matchings of G such that the complement of their union is an acyclic subgraph of G. Unfortunately, this conjecture is not true: Jin, Steffen, and Mazzuoccolo later showed that there exists a counterexample admitting 2-cuts. Here we show that, despite of this, every cyclically 3-edge-connected cubic graph satisfies this second conjecture.- 12 February 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (1) , 1-21
Open AccessThree-Cuts are a Charm: Acyclicity in 3-Connected Cubic Graphs
Let G be a bridgeless cubic graph. In 2023, the three authors solved a conjecture (also known as the $$S_4$$ -Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchings of G such that the complement of their union is a bipartite subgraph of G. They actually show that given any $$1^+$$ -factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G, there exists a perfect matching M of G containing e such that $$G\setminus (F\cup M)$$ is bipartite. This is a step closer to comprehend better the Fan–Raspaud Conjecture and eventually the Berge–Fulkerson Conjecture. The $$S_4$$ -Conjecture, now a theorem, is also the weakest assertion in a series of three conjectures made by Mazzuoccolo in 2013, with the next stronger statement being: there exist two perfect matchings of G such that the complement of their union is an acyclic subgraph of G. Unfortunately, this conjecture is not true: Jin, Steffen, and Mazzuoccolo later showed that there exists a counterexample admitting 2-cuts. Here we show that, despite of this, every cyclically 3-edge-connected cubic graph satisfies this second conjecture. - 1 January 2025
- Published by AGH University Press in Opuscula Mathematica
- Vol. 45 (1) , 103-111
Note on robust coloring of planar graphs
We consider the robust chromatic number \(\chi_1(G)\) of planar graphs \(G\) and show that there exists an infinite family of planar graphs \(G\) with \(\chi_1(G) = 3\), thus solving a recent problem of Bacsó et al. from [The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89].- 1 January 2025
- Published by AGH University Press in Opuscula Mathematica
- Vol. 45 (1) , 103-111
Note on robust coloring of planar graphs
We consider the robust chromatic number \(\chi_1(G)\) of planar graphs \(G\) and show that there exists an infinite family of planar graphs \(G\) with \(\chi_1(G) = 3\), thus solving a recent problem of Bacsó et al. from [The robust chromatic number of graphs, Graphs Combin. 40 (2024), #89].- Open Access
Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan--Raspaud Conjecture (1994), which states that $G$ admits three perfect matchings such that every edge of $G$ belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that $G$ admits two perfect matchings whose deletion yields a bipartite subgraph of $G$. It can be shown that given an arbitrary perfect matching of $G$, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan--Raspaud and the Berge--Fulkerson conjectures, respectively. In this paper, we show that given any $1^+$-factor $F$ (a spanning subgraph of $G$ such that its vertices have degree at least 1) and an arbitrary edge $e$ of $G$, there always exists a perfect matching $M$ of $G$ containing $e$ such that $G\setminus (F\cup M)$ is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in $G$, there exists a perfect matching of $G$ containing at least one edge of each circuit in this collection.Open AccessDisjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan--Raspaud Conjecture (1994), which states that $G$ admits three perfect matchings such that every edge of $G$ belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that $G$ admits two perfect matchings whose deletion yields a bipartite subgraph of $G$. It can be shown that given an arbitrary perfect matching of $G$, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan--Raspaud and the Berge--Fulkerson conjectures, respectively. In this paper, we show that given any $1^+$-factor $F$ (a spanning subgraph of $G$ such that its vertices have degree at least 1) and an arbitrary edge $e$ of $G$, there always exists a perfect matching $M$ of $G$ containing $e$ such that $G\setminus (F\cup M)$ is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in $G$, there exists a perfect matching of $G$ containing at least one edge of each circuit in this collection. - 7 June 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (10)
Subcubic planar graphs of girth 7 are class I
- 7 June 2022
- Published by Elsevier in Discrete Mathematics
- Vol. 345 (10)
Subcubic planar graphs of girth 7 are class I
- Open Access
Subcubic planar graphs of girth 7 are class I
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 from 1974.
Open AccessSubcubic planar graphs of girth 7 are class I
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 from 1974.
- Open Access
Circular (4 − \epsilon)-coloring of some classes of signed graphs
A circular r-coloring of a signed graph (G, σ) is an assignment φ of points of a circle C r of circumference r to the vertices of (G, σ) such that for each positive edge uv of (G, σ) the distance of φ(v) and φ(v) is at least 1 and for each negative edge uv the distance of φ(u) from the antipodal of φ(v) is at least 1. The circular chromatic number of (G, σ), denoted χ c (G, σ), is the infimum of r such that (G, σ) admits a circular r-coloring. This notion is recently defined by Naserasr, Wang, and Zhu who, among other results, proved that for any signed d-degenerate simple graphĜ we have χ c (Ĝ) ≤ 2d. For d ≥ 3, examples of signed d-degenerate simple graphs of circular chromatic number 2d are provided. But for d = 2 only examples of signed 2-degenerate simple graphs of circular chromatic number close enough to 4 are given, noting that these examples are also signed bipartite planar graphs. In this work we first observe the following restatement of the 4-color theorem: If (G, σ) is a signed bipartite planar simple graph where vertices of one part are all of degree 2, then χ c (G, σ) ≤ 16 5. Motivated by this observation, we provide an improved upper bound of 4 − 2 n+1 2 for the circular chromatic number of a signed 2-degenerate simple graph on n vertices and an improved upper bound of 4 − 4 n+2 2 for the circular chromatic number of a signed bipartite planar simple graph on n vertices. We then show that each of the bounds is tight for any value of n ≥ 4.
Open AccessCircular (4 − \epsilon)-coloring of some classes of signed graphs
A circular r-coloring of a signed graph (G, σ) is an assignment φ of points of a circle C r of circumference r to the vertices of (G, σ) such that for each positive edge uv of (G, σ) the distance of φ(v) and φ(v) is at least 1 and for each negative edge uv the distance of φ(u) from the antipodal of φ(v) is at least 1. The circular chromatic number of (G, σ), denoted χ c (G, σ), is the infimum of r such that (G, σ) admits a circular r-coloring. This notion is recently defined by Naserasr, Wang, and Zhu who, among other results, proved that for any signed d-degenerate simple graphĜ we have χ c (Ĝ) ≤ 2d. For d ≥ 3, examples of signed d-degenerate simple graphs of circular chromatic number 2d are provided. But for d = 2 only examples of signed 2-degenerate simple graphs of circular chromatic number close enough to 4 are given, noting that these examples are also signed bipartite planar graphs. In this work we first observe the following restatement of the 4-color theorem: If (G, σ) is a signed bipartite planar simple graph where vertices of one part are all of degree 2, then χ c (G, σ) ≤ 16 5. Motivated by this observation, we provide an improved upper bound of 4 − 2 n+1 2 for the circular chromatic number of a signed 2-degenerate simple graph on n vertices and an improved upper bound of 4 − 4 n+2 2 for the circular chromatic number of a signed bipartite planar simple graph on n vertices. We then show that each of the bounds is tight for any value of n ≥ 4.
- 11 January 2021
- Published by Wiley in Journal of Graph Theory
- Vol. 97 (3) , 382-392
At least half of the leapfrog fullerene graphs have exponentially many Hamilton cycles
A fullerene graph is a 3‐connected cubic planar graph with pentagonal and hexagonal faces. The leapfrog transformation of a planar graph produces the dual of the truncation of the given graph. A fullerene graph is a leapfrog if it can be obtained from another fullerene graph by the leapfrog transformation. We prove that leapfrog fullerene graphs on vertices have at least Hamilton cycles.- 11 January 2021
- Published by Wiley in Journal of Graph Theory
- Vol. 97 (3) , 382-392
At least half of the leapfrog fullerene graphs have exponentially many Hamilton cycles
A fullerene graph is a 3‐connected cubic planar graph with pentagonal and hexagonal faces. The leapfrog transformation of a planar graph produces the dual of the truncation of the given graph. A fullerene graph is a leapfrog if it can be obtained from another fullerene graph by the leapfrog transformation. We prove that leapfrog fullerene graphs on vertices have at least Hamilton cycles.