Header menu link for other important links
X
On induced colourful paths in triangle-free graphs
, M. Basavaraju, L.S. Chandran, M.C. Francis
Published in Elsevier B.V.
2019
Volume: 255
   
Pages: 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.
Figures & Tables (3)
  • Figure-0
    Figure 1: The forced vertices when k = 4.
  • Figure-1
    Figure 3: The forced vertices when k = 6. The vertices ... Expand
  • Figure-2
    Figure 2: The forced vertices when k = 5. The vertices ... Expand
About the journal
JournalData powered by SciSpaceDiscrete Applied Mathematics
PublisherData powered by SciSpaceElsevier B.V.
ISSN0166218X