(ÚNKP-23-4-SZTE-628) Támogató: Kulturális és Innovációs Minisztérium
Szakterületek:
Diszkrét matematika és kombinatorika
A well known problem from an excellent book of Lovász states that any hypergraph with
the property that no pair of hyperedges intersect in exactly one vertex can be properly
2-colored. Motivated by this as well as recent works of Keszegh and of Gyárfás et
al we study the 1-intersection graph of a hypergraph. The 1-intersection graph encodes
those pairs of hyperedges in a hypergraph that intersect in exactly one vertex. We
prove for k∈{2,4} that all hypergraphs whose 1-intersection graph is k-partite can
be properly k-colored.
