KARDOŠ , František

A facial parity edge colouring of a connected bridgeless plane graph is an edge colouring in which no two face-adjacent edges (consecutive edges of a facial walk of some face) receive the same colour, in addition, for each face α and each colour c, either no edge or an odd number of edges incident with α is coloured with c. From Vizing's...

Lovász 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 Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008, but in general only linear bounds are known. In this paper, we provide the first superlinear...

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 at least 0.4352n. Our bound on the independence number is valid for random cubic graphs as well, as it improves existing lower bounds on the maximum cut in cubic...

A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. [Discrete Math. 311 (2011) 512-520] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at...

The dissociation number of a graph G is the number of vertices in a maximum size induced subgraph of G with vertex degree at most 1. A k-path vertex cover of a graph G is a subset S of vertices of G such that every path of order k in G contains at least one vertex from S. The minimum 3-path vertex cover is a dual problem to the dissociation...

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 P_k(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining P_k(G) is NP-hard for each k ≥ 2, while for trees the problem can be solved in linear time. We...

A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint...

We show that every cubic bridgeless graph G has at least 2|V(G)|/3656 perfect matchings. This confirms an old conjecture of Lovász and Plummer.