7 citations · 33 across the 16 of their papers we have counts for
17 papers · 1 filter
A tris of perfect matchings in bridgeless claw-free cubic graphs
Jean Paul Zerafa
A proof of the cycle double cover conjecture was recently announced, yielding an -cycle double cover for every bridgeless graph. The stronger -cycle double cover conjecture,…
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…
The Pairing-Hamiltonian property in graph prisms
Marién Abreu, Giuseppe Mazzuoccolo, Federico Romaniello +1
Let be a graph of even order, and consider as the complete graph on the same vertex set as . A perfect matching of is called a pairing of . If for every pairi…
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…
On two graph isomorphism problems
John Baptist Gauci, Jean Paul Zerafa
In 2015, Bogdanowicz gave a necessary and sufficient condition for a 4-regular circulant graph to be isomorphic to the Cartesian product of two cycles. Accordion graphs, denoted by…
On the existence of graphs which can colour every regular graph
Giuseppe Mazzuoccolo, Gloria Tabarelli, Jean Paul Zerafa
Let and be graphs. An -colouring of is a proper edge-colouring such that for any vertex there exists a vertex with $…
Betwixt and between 2-factor Hamiltonian and Perfect-Matching-Hamiltonian graphs
Federico Romaniello, Jean Paul Zerafa
A Hamiltonian graph is 2-factor Hamiltonian (2FH) if each of its 2-factors is a Hamiltonian cycle. A similar, but weaker, property is the Perfect-Matching-Hamiltonian property (PMH…
Perfect matchings, Hamiltonian cycles and edge-colourings in a class of cubic graphs
Marién Abreu, John Baptist Gauci, Domenico Labbate +2
A graph has the Perfect-Matching-Hamiltonian property (PMH-property) if for each one of its perfect matchings, there is another perfect matching of such that the union of t…
Saved by the rook: a case of matchings and Hamiltonian cycles
Marién Abreu, John Baptist Gauci, Jean Paul Zerafa
The rook graph is a graph whose edges represent all the possible legal moves of the rook chess piece on a chessboard. The problem we consider is the following. Given any set co…
The Erdős--Faber--Lovász Conjecture revisited
John Baptist Gauci, Jean Paul Zerafa
The Erdős--Faber--Lovász Conjecture, posed in 1972, states that if a graph is the union of cliques of order (referred to as defining -cliques) such that two cliques…
Ban--Linial's Conjecture and treelike snarks
Jean Paul Zerafa
A bridgeless cubic graph is said to have a 2-bisection if there exists a 2-vertex-colouring of (not necessarily proper) such that: (i) the colour classes have the same card…
A note on fractional covers of a graph
John Baptist Gauci, Jean Paul Zerafa
A fractional colouring of a graph is a function that assigns a non-negative real value to all possible colour-classes of containing any vertex of , such that the sum of…
Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants
John Baptist Gauci, Jean Paul Zerafa
Let be a graph of even order and let be the complete graph on the same vertex set of . A pairing of a graph is a perfect matching of the graph . A graph $…
Perfect matchings and Hamiltonicity in the Cartesian product of cycles
John Baptist Gauci, Jean Paul Zerafa
A pairing of a graph is a perfect matching of the complete graph having the same vertex set as . If every pairing of can be extended to a Hamiltonian cycle of the underl…
Some snarks are worse than others
Edita Máčajová, Giuseppe Mazzuoccolo, Vahan Mkrtchyan +1
Many conjectures and open problems in graph theory can either be reduced to cubic graphs or are directly stated for cubic graphs. Furthermore, it is known that for a lot of problem…
Extending perfect matchings to Hamiltonian cycles in line graphs
Marién Abreu, John Baptist Gauci, Domenico Labbate +2
A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cy…
An equivalent formulation of the Fan-Raspaud Conjecture and related problems
Giuseppe Mazzuoccolo, Jean Paul Zerafa
In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question…