Affordable Access

Trees in greedy colorings of hypergraphs

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Volume
311
Identifiers
DOI: 10.1016/j.disc.2010.10.017
Keywords
  • Greedy Coloring
  • Chromatic Number
  • Subtrees In Graphs
Disciplines
  • Computer Science

Abstract

Abstract It is a well-known proposition that every graph of chromatic number larger than t contains every tree with t edges. The ‘standard’ reasoning is that such a graph must contain a subgraph of minimum degree at least t . Bohman, Frieze and Mubayi noticed that although this argument does not work for hypergraphs, it is still possible that the proposition holds for hypergraphs as well. Indeed, Po-Shen Loh recently proved that every uniform hypergraph of chromatic number larger than t contains every hypertree with t edges. Here we observe that the basic property of the well-known greedy algorithm implies immediately a much more general result (with a conceptually simpler proof): if the greedy algorithm colors the vertices of an r -uniform hypergraph with more than t colors then the hypergraph contains every r -uniform hypertree with t edges.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Trees in greedy colorings of hypergraphs

on Discrete Mathematics Jan 01, 2011

Greedy colorings of words

on Discrete Applied Mathematics

GreedyF-colorings of graphs

on Discrete Mathematics Jan 01, 2003
More articles like this..