Tung H. Nguyen

collaborators

2 papers

math.CO2025

Polynomial $χ$ -boundedness for excluding $P_{5}$

Tung H. Nguyen

Resolving a 1985 open problem of Gyárfás, we prove that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path $P_{5}$ . Our approach in…

math.CO2025

Fractionally colouring $P_{5}$ -free graphs

Tung H. Nguyen

We obtain some $d \geq 2$ such that every graph $G$ with no induced copy of the five-vertex path $P_{5}$ has at most $α (G) ω (G)^{d}$ vertices. This ``off-diagonal Ramsey'' statement implie…

Polynomial χ-boundedness for excluding P5​

Fractionally colouring P5​-free graphs

Polynomial $χ$ -boundedness for excluding $P_{5}$

Fractionally colouring $P_{5}$ -free graphs