Chromatic number of graphs each path of which is 3-colourable (Q1601403)

\textit{A. Gyárfás} [Fruit salad, Electron. J. Comb. 4, Research paper R8 (1997; Zbl 0885.05103); printed version J. Comb. 4, 65-72 (1997)] conjectured that a graph in which each path spans a \(3\)-chromatic subgraph is \(k\)-colorable, for a constant \(k\) (possibly \(k= 4\)). The authors prove that such a graph \(G\) is colorable with \(3\cdot\lfloor\lg_c|V(G)|\rfloor\) colors for a suitable constant \(c = 8/7\).