Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths

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

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: We prove that for all nonnegative integers k,s there exists c with the following property. Let G be a graph with clique number at most k and chromatic number more than c. Then 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. This extends a recent result of Gyarfas and Sarkozy, who proved the same (when k=2) for graphs G with girth at least five.

Review text

Summary: We prove that for all integers \(\kappa, s\geq 0\) there exists \(c\) with the following property. Let \(G\) be a graph with clique number at most \(\kappa\) and chromatic number more than \(c\). Then 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. This extends a recent result of \textit{A. Gyárfás} and \textit{G. Sárközy} [Electron. J. Comb. 23, No. 4, Research Paper P4.46, 5 p. (2016)] who proved the same for graphs \(G\) with \(\kappa=2\) and girth at least five. For Part II see [\textit{M. Chudnovsky} et al., J. Comb. Theory, Ser. B 118, 109--128 (2016; Zbl 1332.05053)].

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths

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