Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Induced Colourful Paths in Triangle-free Graphs
Speaker:Mathew Francis
coming from:Indian Statistical Institute, Chennai, India
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 14 September 2017
Duration:30 Minutes
Building:E1 4
Given a graph G = (V, E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on \chi(G) vertices, where \chi(G) is the chromatic number of G. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on \chi(G) vertices.
Name(s):Davis Issac
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Davis Issac, 09/06/2017 03:50 PM
Last modified:
halma/MPII/DE, 04/16/2019 12:00 AM
  • Davis Issac, 09/06/2017 03:50 PM -- Created document.