{
  "id": "1604.06070",
  "version": "v1",
  "published": "2016-04-20T19:31:17.000Z",
  "updated": "2016-04-20T19:31:17.000Z",
  "title": "On Induced Colourful Paths in Triangle-free Graphs",
  "authors": [
    "Jasine Babu",
    "Manu Basavaraju",
    "L. Sunil Chandran",
    "Mathew C. Francis"
  ],
  "categories": [
    "math.CO"
  ],
  "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 Theorem that every properly coloured graph contains a colourful path on $\\chi(G)$ vertices. It is interesting to think of what analogous result one could obtain if one considers induced colourful paths instead of just colourful paths. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $\\chi(G)$ vertices. As proving this conjecture in its fullest generality seems to be difficult, we study a special case of the conjecture. We show that the conjecture is true when the girth of $G$ is equal to $\\chi(G)$. Even this special case of the conjecture does not seem to have an easy proof: our method involves a detailed analysis of a special kind of greedy colouring algorithm. This result settles the conjecture for every properly coloured triangle-free graph $G$ with girth at least $\\chi(G)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-04-20T19:31:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "G.2.2"
    ],
    "keywords": [
      "induced colourful path",
      "properly coloured triangle-free graph",
      "conjecture",
      "special case",
      "properly coloured graph contains"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160406070B"
    }
  }
}