Separating tree-chromatic number from path-chromatic number

DOI10.1016/J.JCTB.2019.02.003zbMATH Open1415.05113arXiv1703.03973OpenAlexW2913680851MaRDI QIDQ2312619FDOQ2312619

Tamás Mészáros, Libby Taylor, Piotr Micek, Heather Smith, Stefan Felsner, Fidel Barrera-Cruz, William T. Trotter

Publication date: 17 July 2019

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We apply Ramsey theoretic tools to show that there is a family of graphs which have tree-chromatic number at most~$2$ while the path-chromatic number is unbounded. This resolves a problem posed by Seymour.

Full work available at URL: https://arxiv.org/abs/1703.03973

zbMATH Keywords

Ramsey theorytree-decompositionbinary tree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Graph Theory and Probability
• A Ramsey theorem for trees
• Tree-chromatic number

Cited In (3)

• Orthogonal Tree Decompositions of Graphs
• Comparing Dushnik-Miller dimension, Boolean dimension and local dimension
• Notes on tree- and path-chromatic number

This page was built for publication: Separating tree-chromatic number from path-chromatic number

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