pith. sign in

arxiv: 1002.4210 · v3 · pith:QFSHETZ2new · submitted 2010-02-22 · 🧮 math.CO

Unique-maximum and conflict-free colorings for hypergraphs and tree graphs

Panagiotis Cheilaris , Bal\'azs Keszegh , D\"om\"ot\"or P\'alv\"olgyi This is my paper
classification 🧮 math.CO
keywords coloringsconflict-freehypergraphsunique-maximumappearscolorcoloringevery
0
0 comments X
read the original abstract

We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color appears only once. In a conflict-free coloring, in every hyperedge of the hypergraph there is a color that appears only once. We define corresponding unique-maximum and conflict-free chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa

    cs.DS 2025-07 unverdicted novelty 7.0

    Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.