Jorik Jooken

Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound

Wouter Cames van Batenburg, Jan Goedgebeur, Jorik Jooken

In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $∣ V (G) ∣/2$ . This long-standing conjecture was recently disproved…

Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples

Jan Goedgebeur, Jorik Jooken, Edita Máčajová +3

In 1988, Jaeger conjectured that every bridgeless cubic graph $G$ admits a Petersen coloring; that is, a map $E (G) \to E (P)$ mapping any two adjacent edges of $G$ to two adjacent e…

On the number of perfect matchings in planar graphs

Jan Goedgebeur, Jorik Jooken, Tibo Van den Eede +1

We investigate the minimum non-zero number of perfect matchings in planar graphs. We prove that this is a constant for 2-connected planar graphs of minimum degree 3 and 3-connected…

Counting Hamiltonian paths between prescribed vertices in traceable graphs with a forbidden induced subgraph

Jorik Jooken, Carol T. Zamfirescu

For graphs $G$ and $F$ , we say that $G$ is $F$ -free if $F$ does not occur as an induced subgraph of $G$ . This paper is concerned with the following question: Given an $F$ -free grap…

Vertex-critical $(P_{5}, chair)$ -free and $(P_{5}, cricket)$ -free graphs

Jorik Jooken

For graphs $G, F_{1}$ and $F_{2}$ , we say that $G$ is $(F_{1}, F_{2})$ -free if neither $F_{1}$ nor $F_{2}$ is an induced subgraph of $G$ . We say that $G$ is $k$ -vertex-critical if the chromatic…

A non-existence result for vertex-girth-regular graphs

Jorik Jooken, Denys Lohvynov

A $k$ -regular graph of girth $g$ is called vertex-girth-regular if every vertex is contained in the same number of cycles of length $g$ . For integers $n, k, g$ and $λ$ , we denote s…

Three-coloring triangle-free graphs without long forbidden paths

Yidong Zhou, Jorik Jooken, Baoyuan Shan +2

A graph $G$ is $k$ -vertex-critical if $χ (G) = k$ , but $χ (G^{'}) < k$ for every proper induced subgraph $G^{'}$ of $G$ . For a family of graphs $F$ , $G$ is $F$ -free if no g…

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification

Tala Eagling-Vose, Jorik Jooken, Felicia Lucke +2

We consider Colouring on graphs that are $H$ -subgraph-free for some fixed graph $H$ , which are graphs that do not contain $H$ as a subgraph. To classify the complexity of Colouring…

On the order-diameter ratio of girth-diameter cages

Stijn Cambie, Jan Goedgebeur, Jorik Jooken +1

For integers $k, g, d$ , a $(k; g, d)$ -cage (or simply girth-diameter cage) is a smallest $k$ -regular graph of girth $g$ and diameter $d$ (if it exists). The order of a $(k; g, d)$ -cage i…

New small regular graphs of given girth: the cage problem and beyond

Geoffrey Exoo, Jan Goedgebeur, Jorik Jooken +2

The cage problem concerns finding $(k, g)$ -graphs, which are $k$ -regular graphs with girth $g$ , of the smallest possible number of vertices. The central goal is to determine $n(k,g)…

Computer-assisted graph theory: a survey

Jorik Jooken

Computers and algorithms play an ever-increasing role in obtaining new results in graph theory. In this survey, we present a broad range of techniques used in computer-assisted gra…

On the extrema of the mean subtree order of graphs

Stijn Cambie, Jorik Jooken, Stephan Wagner

It has been conjectured that the minimum and maximum of the mean subtree order among connected graphs of order $n$ are attained by the path $P_{n}$ and clique $K_{n}$ , respectively. Ex…

Improved lower bounds on the maximum size of graphs with girth 5

Jan Goedgebeur, Jorik Jooken, Gwenaël Joret +1

We present a new algorithm for improving lower bounds on $e x (n; {C_{3}, C_{4}})$ , the maximum size (number of edges) of an $n$ -vertex graph of girth at least 5. The core of our algorit…

Counting Small Cycle Double Covers

Jorik Jooken, Ben Seamone, Carol T. Zamfirescu

A theorem due to Seyffarth states that every planar $4$ -connected $n$ -vertex graph has a cycle double cover (CDC) containing at most $n - 1$ cycles (a "small" CDC). We extend this th…

On a conjecture of Faudree and Schelp

Jan Goedgebeur, Jorik Jooken, Michiel Provoost +1

In 1976 Faudree and Schelp conjectured that in a hamiltonian-connected graph on $n$ vertices, any two distinct vertices are connected by a path of length $k$ for every $k \geq n /2$ .…

There are finitely many $5$ -vertex-critical $(P_{6}, bull)$ -free graphs

Yiao Ju, Jorik Jooken, Jan Goedgebeur +1

In this paper, we are interested in $4$ -colouring algorithms for graphs that do not contain an induced path on $6$ vertices nor an induced bull, i.e., the graph with vertex set $\{…

The Gray graph is pseudo 2-factor isomorphic

Marien Abreu, Jan Goedgebeur, Jorik Jooken +2

A graph is pseudo 2-factor isomorphic if all of its 2-factors have the same parity of number of cycles. Abreu et al. [J. Comb. Theory, Ser. B. 98 (2008) 432--442] conjectured that…

Sharp results for the Erdős, Pach, Pollack and Tuza problem

Stijn Cambie, Jorik Jooken

We consider the Erdős, Pach, Pollack and Tuza problem, asking for the maximum diameter of a graph with given order $n$ , minimum degree $δ$ and clique number at most $ω$ . We solve t…

Critical $(P_{5}, W_{4})$ -Free Graphs

Wen Xia, Jorik Jooken, Jan Goedgebeur +3

A graph $G$ is $k$ -vertex-critical if $χ (G) = k$ but $χ (G - v) < k$ for all $v \in V (G)$ . A graph is $(H_{1}, H_{2})$ -free if it contains no induced subgraph isomorphic to $H_{1}$ nor $H_{2}$ .…

Computational methods for finding bi-regular cages

Jan Goedgebeur, Jorik Jooken, Tibo Van den Eede

An $({r, m}; g)$ -graph is a (simple, undirected) graph of girth $g \geq 3$ with vertices of degrees $r$ and $m$ where $2 \leq r < m$ . Given $r, m, g$ , we seek the $({r, m}; g)$ -graphs…

On $(k, g)$ -Graphs without $(g + 1)$ -Cycles

Leonard Chidiebere Eze, Robert Jajcay, Jorik Jooken

A $(k, g, g + 1)$ -graph is a $k$ -regular graph of girth $g$ which does not contain cycles of length $g + 1$ . Such graphs are known to exist for all parameter pairs $k \geq 3,…

math.CO2024★ 1 cited

On graphs isomorphic with their conduction graph

Aidan Birkinshaw, Patrick W. Fowler, Jan Goedgebeur +1

Conduction graphs are defined here in order to elucidate at a glance the often complicated conduction behaviour of molecular graphs as ballistic molecular conductors. The graph $G^…

On the girth and connectivity of cubic graphs with a unique longest cycle

Jorik Jooken, Carol T. Zamfirescu

We show that there exists an infinite family of cubic $2$ -connected non-hamiltonian graphs with girth $5$ containing a unique longest cycle.