Separating tree-chromatic number from path-chromatic number

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Sep 2019Embargo end date: 01 Jan 2017 Poland English Publisher:Elsevier BVJournal:Journal of Combinatorial Theory, Series B, volume 138, pages 206-218 (issn: 0095-8956,

Copyright policy )Funded by:NSF | MCTP: A Postdoctoral Prog...

Authors: Fidel Barrera-Cruz; Stefan Felsner; Tamás Mészáros 0001; Piotr Micek; Heather C. Smith; Libby Taylor; William T. Trotter;

doi: 10.1016/j.jctb.2019.02.003 , 10.48550/arxiv.1703.03973

arXiv: 1703.03973

Separating tree-chromatic number from path-chromatic number

- Summary
- Subjects
- Related research
  (2)
- Metrics

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.

reviewers comments included

Country

Poland

Related Organizations

Georgia Institute of Technology
United States
Freie Universität Berlin
Germany
Technical University of Berlin
Germany
Jagiellonian University
Poland
Davidson College
United States

View all View all

Keywords

binary tree, Coloring of graphs and hypergraphs, tree-decomposition, Ramsey theory, FOS: Mathematics, Generalized Ramsey theory, Mathematics - Combinatorics, Combinatorics (math.CO)

2 Research products, page 1 of 1

Notes on Tree- and Path-Chromatic Number
2021IsAmongTopNSimilarDocuments
Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number^*
2017IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	2
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average