Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs

Cheilaris, Panagiotis and Keszegh, Balázs and Pálvölgyi, Dömötör (2013) Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs. SIAM Journal on Discrete Mathematics, 27 (4). pp. 1775-1787. ISSN 0895-4801

Preview

Text cfumhyptjsiam.pdf Download (311kB) | Preview

Abstract

We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum (UM) colorings and conflict-free (CF) colorings. In a UM coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color in the hyperedge occurs in only one vertex of the hyperedge. In a CF coloring, in every hyperedge of the hypergraph there exists a color in the hyperedge that occurs in only one vertex of the hyperedge. We consider the corresponding UM and CF chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs. Read More: http://epubs.siam.org/doi/abs/10.1137/120880471

Actions (login required)

Edit Item