Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.00189 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912253243031552 |
|---|---|
| author | Szabó, Balázs István |
| author_facet | Szabó, Balázs István |
| contents | A directed hypergraph is a hypergraph in which the vertex set of each hyperedge is partitioned into two disjoint parts, a head and a tail. Keszegh and Pálvölgyi posed the following conjecture. Let $H$ be a directed hypergraph such that in every hyperedge the number of head-vertices is less than the number of tail-vertices and assume that for every pair of hyperedges $e_{1},e_{2}\in E(H)$ with $|e_{1}\cap e_{2}|=1$, the common vertex is a head-vertex in at least one of the hyperedges. Then $H$ admits a proper 2-coloring. Keszegh showed that the conjecture is also true in the special case of 3-uniform hypergraphs. A directed hypergraph is called one-headed if every hyperedge has exactly one head-vertex. The main result of this paper is that the conjecture is true for one-headed directed hypergraphs with all hyperedges having size at least three.
Directed 3-uniform hypergraphs such that in every hyperedge the number of head-vertices is one and the number of tail-vertices is two are called $2\rightarrow 1$ hypergraphs. In this paper we consider sufficient conditions for $2\rightarrow 1$ hypergraphs to be proper $k$-colorable for some small $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_00189 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coloring one-headed directed hypergraphs Szabó, Balázs István Combinatorics A directed hypergraph is a hypergraph in which the vertex set of each hyperedge is partitioned into two disjoint parts, a head and a tail. Keszegh and Pálvölgyi posed the following conjecture. Let $H$ be a directed hypergraph such that in every hyperedge the number of head-vertices is less than the number of tail-vertices and assume that for every pair of hyperedges $e_{1},e_{2}\in E(H)$ with $|e_{1}\cap e_{2}|=1$, the common vertex is a head-vertex in at least one of the hyperedges. Then $H$ admits a proper 2-coloring. Keszegh showed that the conjecture is also true in the special case of 3-uniform hypergraphs. A directed hypergraph is called one-headed if every hyperedge has exactly one head-vertex. The main result of this paper is that the conjecture is true for one-headed directed hypergraphs with all hyperedges having size at least three. Directed 3-uniform hypergraphs such that in every hyperedge the number of head-vertices is one and the number of tail-vertices is two are called $2\rightarrow 1$ hypergraphs. In this paper we consider sufficient conditions for $2\rightarrow 1$ hypergraphs to be proper $k$-colorable for some small $k$. |
| title | Coloring one-headed directed hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.00189 |