Chromatic number of graphs each path of which is 3-colourable (Q1601403)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Chromatic number of graphs each path of which is 3-colourable |
scientific article; zbMATH DE number 1760649
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Chromatic number of graphs each path of which is 3-colourable |
scientific article; zbMATH DE number 1760649 |
Statements
Chromatic number of graphs each path of which is 3-colourable (English)
0 references
18 March 2003
0 references
\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\).
0 references
coloring
0 references
