Ben Cameron

activity

20222026

collaborators

Showing math.COShow all

7 papers · 1 filter

math.CO2026

Obstructions to $k$ -colouring $H$ -free graphs

Iain Beaton, Ben Cameron, Adam van Omme

A graph is $H$ -free if it has no induced subgraph isomorphic to $H$ . In 2020, Chudnovsky, Goedgebeur, Schaudt, and Zhong characterized all graphs $H$ such that there are only finit…

math.CO2026

A dichotomy for the number of vertex-critical ( $P_{5}$ , $H$ )-free graphs when $H$ is bipartite

Iain Beaton, Ben Cameron

A graph $G$ is $k$ -vertex-critical if $χ (G) = k$ , but $χ (H) < k$ for every induced subgraph $H$ of $G$ . A graph $G$ is $(H_{1}, H_{2}, \dots, H_{m})$ -free if does not contain $H_{i}$ as an induce…

math.CO2026

Vertex-critical graphs in subfamilies of $(P_{4} + ℓ P_{1})$ -free graphs

Iain Beaton, Ben Cameron

A graph $G$ is $k$ -vertex-critical if $χ (G) = k$ but $χ (G - v) < k$ for all $v \in V (G)$ . In this paper we make progress on the open problem of the finiteness of $k$ -vertex-critical $(P_4…

math.CO2025

On Gyárfás' Path-Colour Problem

Ben Cameron, Alexander Clow

In their 1997 paper titled ``Fruit Salad", Gyárfás posed the following conjecture: there exists a constant $k$ such that if each path of a graph spans a $3$ -colourable subgraph, th…

math.CO2025

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}$ .…

math.CO2024

Vertex-critical graphs in co-gem-free graphs

Iain Beaton, Ben Cameron

A graph $G$ is $k$ -vertex-critical if $χ (G) = k$ but $χ (G - v) < k$ for all $v \in V (G)$ and $(G, H)$ -free if it contains no induced subgraph isomorphic to $G$ or $H$ . We show that there a…

math.CO2022

A Tight Upper Bound on the Average Order of Dominating Sets of a Graph

Iain Beaton, Ben Cameron

In this paper we study the the average order of dominating sets in a graph, $avd (G)$ . Like other average graph parameters, the extremal graphs are of interest. Beato…

Obstructions to k-colouring H-free graphs

A dichotomy for the number of vertex-critical (P5​, H)-free graphs when H is bipartite

Vertex-critical graphs in subfamilies of (P4​+ℓP1​)-free graphs

On Gyárfás' Path-Colour Problem

Critical (P5​,W4​)-Free Graphs

Vertex-critical graphs in co-gem-free graphs

A Tight Upper Bound on the Average Order of Dominating Sets of a Graph

Obstructions to $k$ -colouring $H$ -free graphs

A dichotomy for the number of vertex-critical ( $P_{5}$ , $H$ )-free graphs when $H$ is bipartite

Vertex-critical graphs in subfamilies of $(P_{4} + ℓ P_{1})$ -free graphs

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