Source author record

František Kardoš

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

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

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.

preprint2022arXiv

Strengthening a theorem of Meyniel

For an integer $k \geq 1$ and a graph $G$ , let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$ -colorings of $G$ , and an edge between two vertices $α$ and~ $β$ whenever the coloring~ $β$ can be obtained from $α$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$ . We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$ .

preprint2022arXiv

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.

preprint2014arXiv

Sandwiching saturation number of fullerene graphs

The saturation number of a graph $G$ is the cardinality of any smallest maximal matching of $G$ , and it is denoted by $s(G)$ . Fullerene graphs are cubic planar graphs with exactly twelve 5-faces; all the other faces are hexagons. They are used to capture the structure of carbon molecules. Here we show that the saturation number of fullerenes on $n$ vertices is essentially $n/3$ .

preprint2010arXiv

Minimum k-path vertex cover

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 k-path vertex cover in G. It is shown that the problem of determining ψ_k(G) is NP-hard for each k \geq 2, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of ψ_k(G) and provide several estimations and exact values of ψ_k(G). We also prove that ψ_3(G) \leq (2n + m)/6, for every graph G with n vertices and m edges.

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.

František Kardoš

Research overview

Is this your work?

5 publications

Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching

Strengthening a theorem of Meyniel

Subcubic planar graphs of girth 7 are class I

Sandwiching saturation number of fullerene graphs

Minimum k-path vertex cover

See the researcher in context

Building this map preview