Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs
| Autor: | Balázs Keszegh, Dömötör Pálvölgyi, Panagiotis Cheilaris |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) Hypergraph Mathematics::Combinatorics General Mathematics Complete coloring Computer Science::Computational Geometry Combinatorics Greedy coloring Computer Science::Discrete Mathematics Fractional coloring Computer Science::Data Structures and Algorithms Conflict free Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics. 27:1775-1787 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/120880471 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|