Chromatic number of graphs each path of which is 3-colourable

DOI10.1007/BF03322762MaRDI QIDQ1601403zbMATH OpenOpenAlexFDO

Authors Bert Randerath, Ingo Schiermeyer

Publication date 18 March 2003

Published in Results in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf03322762

zbMATH Keywords

coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Review text

\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\).

Recommendations

• Colorful paths for 3-chromatic graphs
• On the chromatic number of path graph P₃(G)
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• On circuits and subgraphs of chromatic graphs

Cites work

• Graph theory with applications

Cited in

(9)

• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Circumference, chromatic number and online coloring
• On the chromatic number of path graph P₃(G)
• Chromatic layout number of paths and cycles
• On graphs with restricted link graphs and the chromatic number at most $3$
• scientific article; zbMATH DE number 4089589 (Why is no real title available?)
• Colorful paths for 3-chromatic graphs
• Path homomorphisms, graph colorings, and Boolean matrices
• Problems close to my heart

This page was built for publication: Chromatic number of graphs each path of which is 3-colourable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1601403)