Hussein Houdrouge

activity

20222026

collaborators

5 papers

math.CO2026

3-Colouring Graphs Excluding a Fixed Minor

Vida Dujmović, Hussein Houdrouge, Pat Morin

We show that, for every fixed graph $H$ , every $n$ -vertex graph $G$ that excludes $H$ as a minor is $3$ -colourable with clustering $O_{H} (n^{4/9})$ . That is, there exists a function…

math.CO2026

2-dimensional unit vector flows

Hussein Houdrouge, Bobby Miraftab, Pat Morin

We study $2$ -dimensional unit vector flows on graphs, that is, nowhere-zero flows that assign to each oriented edge a unit vector in $R^{3}$ . We give a new geometric charac…

math.CO2025

Separation Number and Treewidth, Revisited

Hussein Houdrouge, Babak Miraftab, Pat Morin

We give a constructive proof of the fact that the treewidth of a graph $G$ is bounded by a linear function of the separation number of $G$ .

math.CO2023

Connected Dominating Sets in Triangulations

Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2

We show that every $n$ -vertex triangulation has a connected dominating set of size at most $10 n /21$ . Equivalently, every $n$ vertex triangulation has a spanning tree with at least…

math.CO2022

Linear versus centred chromatic numbers

Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2

$\DeclareMathOperator{\chicen}{χ_{\mathrm{cen}}}\DeclareMathOperator{\chilin}{χ_{\mathrm{lin}}}$ A centred colouring of a graph is a vertex colouring in which every connected subgr…