Please use this identifier to cite or link to this item:
https://idr.l2.nitk.ac.in/jspui/handle/123456789/12360
Title: | On induced colourful paths in triangle-free graphs |
Authors: | Babu, J. Basavaraju, M. Chandran, L.S. Francis, M.C. |
Issue Date: | 2019 |
Citation: | Discrete Applied Mathematics, 2019, Vol.255, , pp.109-116 |
Abstract: | 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 Vitaver Theorem that every properly coloured graph contains a colourful path on ?(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on ?(G) vertices and prove its correctness when the girth of G is at least ?(G). Recent work on this conjecture by Gy rf s and S rk zy, and Scott and Seymour has shown the existence of a function f such that if ?(G)?f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. 2018 Elsevier B.V. |
URI: | http://idr.nitk.ac.in/jspui/handle/123456789/12360 |
Appears in Collections: | 1. Journal Articles |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.