# On Induced Colourful Paths in Triangle-free Graphs

@article{Babu2017OnIC, title={On Induced Colourful Paths in Triangle-free Graphs}, author={Jasine Babu and Manu Basavaraju and L. Sunil Chandran and Mathew C. Francis}, journal={Electron. Notes Discret. Math.}, year={2017}, volume={61}, pages={69-75} }

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 χ(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… Expand

#### Topics from this paper

#### 4 Citations

On induced colourful paths in triangle-free graphs

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2019

A conjecture is explored that states that every properly coloured triangle-free graph G contains an induced colourful path on χ ( G ) vertices and is proved to be correctness when the girth of G is at least φ ( G ), which is a corollary of the Gallai–Roy–Vitaver Theorem. Expand

Structure and colour in triangle-free graphs

- Computer Science, Mathematics
- Electron. J. Comb.
- 2021

It is proved that every properly coloured triangle-free graph of chromatic number $\chi$ contains a rainbow independent set of size $\lceil\frac12\chi\rceil$ which is sharp up to a factor $2$. Expand

Induced Subgraphs of Graphs with Large Chromatic Number IX: Rainbow Paths

- Mathematics, Computer Science
- Electron. J. Comb.
- 2017

It is proved that for all nonnegative integers k,s there exists c with the following property: for every vertex-colouring (not necessarily optimal) of G, some induced subgraph of G is an s-vertex path, and all its vertices have different colours. Expand

Variants of the Gy\`arf\`as-Sumner Conjecture: Oriented Trees and Rainbow Paths

- Mathematics, Computer Science
- 2021

Given a finite family F of graphs, we say that a graph G is “F-free” if G does not contain any graph in F as a subgraph. We abbreviate F-free to just “F -free” when F = {F}. A vertex-coloured graph H… Expand

#### References

SHOWING 1-10 OF 10 REFERENCES

Induced Colorful Trees and Paths in Large Chromatic Graphs

- Mathematics, Computer Science
- Electron. J. Comb.
- 2016

Here the following weaker result is proved providing some evidence towards the conjecture that in every proper coloring of a-chromatic triangle-free graph there is an induced colorful path P_k. Expand

Colorful induced subgraphs

- Computer Science, Mathematics
- Discret. Math.
- 1992

It is proved that there exists a function f(k, n) such that for any colored graph G, if χ(G)>f(ω(G), n) then G induces either a colorful out directed star with n leaves or a colorful directed path on n vertices. Expand

A Generalization of the Gallai–Roy Theorem

- Mathematics, Computer Science
- Graphs Comb.
- 2001

For graphs, a positive answer to the following question of Fajtlowicz is given: if G is a graph with chromatic number χ(G), then for any proper coloring of G of χ (G) colors and for any vertex v∈V(G, there is a path P starting at v which represents all χ(_) colors. Expand

Rainbow Paths with Prescribed Ends

- Mathematics, Computer Science
- Electron. J. Comb.
- 2011

It is proved that every connected graph with at least one edge has a proper $k-coloring (for some $k$) such that every vertex of color $i$ has a neighbor of color$i+1$ (mod $k) along each edge. Expand

Induced Subgraphs of Graphs with Large Chromatic Number IX: Rainbow Paths

- Mathematics, Computer Science
- Electron. J. Comb.
- 2017

It is proved that for all nonnegative integers k,s there exists c with the following property: for every vertex-colouring (not necessarily optimal) of G, some induced subgraph of G is an s-vertex path, and all its vertices have different colours. Expand

Introduction to Graph Theory

- Mathematics
- 1995

1. Fundamental Concepts. What Is a Graph? Paths, Cycles, and Trails. Vertex Degrees and Counting. Directed Graphs. 2. Trees and Distance. Basic Properties. Spanning Trees and Enumeration.… Expand

Induced subtrees in graphs of large chromatic number

- Computer Science, Mathematics
- Discret. Math.
- 1980

Our paper proves special cases of the following conjecture: for any fixed tree T there exists a natural number f = f (T) to that every triangle-free graph of chromaticnumber f(T) contains T as an… Expand

Graph Theory

- Computer Science
- Graduate Texts in Mathematics
- 2008

This book provides a systematic treatment of the theory of graphs without sacrificing its intuitive and aesthetic appeal, and is suitable as a textbook for advanced undergraduate and beginning graduate students in mathematics and computer science. Expand

Graph theory, Graduate texts

- 2007