Half-integral Erdős-Pósa property for non-null $S$-$T$ paths
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914928778018816 |
|---|---|
| author | Chekan, Vera Geniet, Colin Hatzel, Meike Pilipczuk, Michał Sokołowski, Marek Seweryn, Michał T. Witkowski, Marcin |
| author_facet | Chekan, Vera Geniet, Colin Hatzel, Meike Pilipczuk, Michał Sokołowski, Marek Seweryn, Michał T. Witkowski, Marcin |
| contents | For a group $Γ$, a $Γ$-labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $Γ$ so that opposite orientations of the same edge are assigned inverse elements. A path in $G$ is non-null if the product of the labels along the path is not the neutral element of $Γ$. We prove that for every finite group $Γ$, non-null $S$-$T$ paths in $Γ$-labelled graphs exhibit the half-integral Erdős-Pósa property. More precisely, there is a function $f$, depending on $Γ$, such that for every $Γ$-labelled graph $G$, subsets of vertices $S$ and $T$, and integer $k$, one of the following objects exists: a family $\cal F$ consisting of $k$ non-null $S$-$T$ paths in $G$ such that every vertex of $G$ participates in at most two paths of $\cal F$; or a set $X$ consisting of at most $f(k)$ vertices that meets every non-null $S$-$T$ path in $G$. This in particular proves that in undirected graphs $S$-$T$ paths of odd length have the half-integral Erdős-Pósa property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16344 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Half-integral Erdős-Pósa property for non-null $S$-$T$ paths Chekan, Vera Geniet, Colin Hatzel, Meike Pilipczuk, Michał Sokołowski, Marek Seweryn, Michał T. Witkowski, Marcin Combinatorics Discrete Mathematics For a group $Γ$, a $Γ$-labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $Γ$ so that opposite orientations of the same edge are assigned inverse elements. A path in $G$ is non-null if the product of the labels along the path is not the neutral element of $Γ$. We prove that for every finite group $Γ$, non-null $S$-$T$ paths in $Γ$-labelled graphs exhibit the half-integral Erdős-Pósa property. More precisely, there is a function $f$, depending on $Γ$, such that for every $Γ$-labelled graph $G$, subsets of vertices $S$ and $T$, and integer $k$, one of the following objects exists: a family $\cal F$ consisting of $k$ non-null $S$-$T$ paths in $G$ such that every vertex of $G$ participates in at most two paths of $\cal F$; or a set $X$ consisting of at most $f(k)$ vertices that meets every non-null $S$-$T$ path in $G$. This in particular proves that in undirected graphs $S$-$T$ paths of odd length have the half-integral Erdős-Pósa property. |
| title | Half-integral Erdős-Pósa property for non-null $S$-$T$ paths |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2408.16344 |