Half-integral Erd\H{o}s-P\'{o}sa property for non-null $S$-$T$ paths
| Autor: | Chekan, Vera, Geniet, Colin, Hatzel, Meike, Pilipczuk, Michał, Sokołowski, Marek, Seweryn, Michał T., Witkowski, Marcin |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | For a group $\Gamma$, a $\Gamma$-labelled graph is an undirected graph $G$ where every orientation of an edge is assigned an element of $\Gamma$ 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 $\Gamma$. We prove that for every finite group $\Gamma$, non-null $S$-$T$ paths in $\Gamma$-labelled graphs exhibit the half-integral Erd\H{o}s-P\'osa property. More precisely, there is a function $f$, depending on $\Gamma$, such that for every $\Gamma$-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\H{o}s-P\'osa property. Comment: 12 pages, 1 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|