Domotor Palvolgyi

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

    Authors: Panagiotis Cheilaris, Domotor Palvolgyi, Balazs Keszegh
    Subjects: Combinatorics
    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
    concentrate in hypergraphs that are induced by paths in tree graphs.

  2. Partitionability to two trees is NP-complete.

    Authors: Domotor Palvolgyi
    Subjects: Computational Complexity
    Abstract

    We show that P2T - the problem of deciding whether the edge set of a simple
    graph can be partitioned into two trees or not - is NP-complete.

Syndicate content