Department of Mathematics

Indian Institute Of Technology Madras , Chennai

Colourful Paths in Graphs

Speaker : Mathew Francis (ISI Chennai)


Abstract :

"A ""proper vertex colouring"" of a graph is an assignment of labels (or ""colours"") to the vertices of a graph such that no two adjacent vertices get the same label. The minimum number of colours required in any proper vertex colouring of a graph $G$ is known as its chromatic number, denoted by $chi(G)$. In a properly vertex coloured graph, we say that a path is a ""colourful path"" if no two vertices on the path have the same colour. Given a properly vertex coloured graph, it is known that there is always a colourful path on $chi(G)$ vertices in it. We conjecture that given any properly vertex coloured triangle-free graph, there is an induced colourful path on $chi(G)$ vertices in the graph and look at various aspects of this conjecture. This talk will be at introductory level. "

Key Speaker Mathew Francis (ISI Chennai)
Place Madhava Hall
Start Time 3:00 PM
Finish Time 4:00 PM
External Link None