research
∙
05/03/2023
Frank number and nowhere-zero flows on graphs
An edge e of a graph G is called deletable for some orientation o if the...
share
research
∙
11/15/2022
Few hamiltonian cycles in graphs with one or two vertex degrees
We fully disprove a conjecture of Haythorpe on the minimum number of ham...
research
∙
10/31/2022
House of Graphs 2.0: a database of interesting graphs and more
In 2012 we announced the House of Graphs (https://houseofgraphs.org) [Di...
research
∙
08/31/2022
A heuristic algorithm for the maximum happy vertices problem using tree decompositions
We propose a new heuristic algorithm for the Maximum Happy Vertices prob...
research
∙
08/12/2021
Some Results on k-Critical P_5-Free Graphs
A graph G is k-vertex-critical if G has chromatic number k but every pro...
research
∙
07/09/2021
New bounds for Ramsey numbers R(K_k-e,K_l-e)
Let R(H_1,H_2) denote the Ramsey number for the graphs H_1, H_2, and let...
research
∙
06/16/2021
Colouring graphs with no induced six-vertex path or diamond
The diamond is the graph obtained by removing an edge from the complete ...
research
∙
05/04/2021
Switching 3-edge-colorings of cubic graphs
The chromatic index of a cubic graph is either 3 or 4. Edge-Kempe switch...
research
∙
01/04/2021
The Minimality of the Georges-Kelmans Graph
In 1971, Tutte wrote in an article that "it is tempting to conjecture th...
research
∙
11/28/2019
Large independent sets in triangle-free cubic graphs: beyond planarity
Every n-vertex planar triangle-free graph with maximum degree at most 3 ...
research
∙
09/21/2019
An algorithm and new bounds for the circular flow number of snarks
It is well-known that the circular flow number of a bridgeless cubic gra...
research
∙
08/30/2019
Existence of regular nut graphs for degree at most 11
A nut graph is a singular graph with one-dimensional kernel and correspo...
research
∙
08/30/2019
Existence of d-regular nut graphs for d at most 11
A nut graph is a singular graph with one-dimensional kernel and correspo...
research
∙
01/30/2019
The smallest nontrivial snarks of oddness 4
The oddness of a cubic graph is the smallest number of odd circuits in a...
research
∙
12/13/2018
Graphs with few Hamiltonian Cycles
We describe an algorithm for the exhaustive generation of non-isomorphic...
research
∙
06/12/2018
On the minimum leaf number of cubic graphs
The minimum leaf number ml (G) of a connected graph G is defined as the ...
research
∙
05/17/2018
Bounds for the smallest k-chromatic graphs of given girth
Let n_g(k) denote the smallest order of a k-chromatic graph of girth at ...
research
∙
04/03/2018
A unified approach to construct snarks with circular flow number 5
The well-known 5-flow Conjecture of Tutte, stated originally for integer...
research
∙
12/21/2017
Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
The family of snarks -- connected bridgeless cubic graphs that cannot be...
research
∙
12/14/2017
Structural and computational results on platypus graphs
A platypus graph is a non-hamiltonian graph for which every vertex-delet...
research
∙
10/02/2017
On the smallest snarks with oddness 4 and connectivity 2
A snark is a bridgeless cubic graph which is not 3-edge-colourable. The ...
research
∙
09/13/2017