Induced colorful trees and paths in large chromatic graphs

MaRDI QIDQ504985zbMATH OpenFDO

Authors András Gyárfás, Gábor N. Sárközy

Publication date 18 January 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p46

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graph coloringsinduced subgraphs

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Review text

Summary: In a proper vertex coloring of a graph a subgraph is colorful if its vertices are colored with different colors. It is well-known that in every proper coloring of a \(k\)-chromatic graph there is a colorful path \(P_k\) on \(k\) vertices. The first author proved in [Zastosow. Mat. 19, No. 3--4, 413--441 (1987; Zbl 0718.05041)] that \(k\)-chromatic and triangle-free graphs have a path \(P_k\) which is an induced subgraph. N. R. Aravind conjectured that these results can be put together: in every proper coloring of a \(k\)-chromatic triangle-free graph, there is an induced colorful \(P_k\). Here we prove the following weaker result providing some evidence towards this conjecture: For a suitable function \(f(k)\), in any proper coloring of an \(f(k)\)-chromatic graph of girth at least five, there is an induced colorful path on \(k\) vertices.

Recommendations

• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Colorful induced subgraphs
• Structure and colour in triangle-free graphs

Cites work

• Colorful induced subgraphs
• Colorful paths for 3-chromatic graphs
• Coloring graphs with locally few colors
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• Induced subtrees in graphs of large chromatic number
• χ‐bounded families of oriented graphs

Cited in

(5)

• Structure and colour in triangle-free graphs
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• Template-driven rainbow coloring of proper interval graphs
• Template-driven rainbow coloring of proper interval graphs
• Variants of the Gyárfás-Sumner conjecture: oriented trees and rainbow paths

This page was built for publication: Induced colorful trees and paths in large chromatic graphs

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