3 papers
math.CO2024
On 3-colourability of -free graphs
Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1
The -colourability problem is a well-known NP-complete problem and it remains NP-complete for -free graphs, where is the graph consisting of with two pendant…
math.CO2024
Directed graphs without rainbow stars
Daniel Gerbner, Andrzej Grzesik, Cory Palmer +1
In a rainbow version of the classical Turán problem one considers multiple graphs on a common vertex set, thinking of each graph as edges in a distinct color, and wants to determin…
math.CO2023
Directed graphs without rainbow triangles
Sebastian Babiński, Andrzej Grzesik, Magdalena Prorok
One of the most fundamental results in graph theory is Mantel's theorem which determines the maximum number of edges in a triangle-free graph of order . Recently a colorful vari…