Skip to main content
added 133 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

It sounds like you are asking if the Erdős–Pósa property holds for frustrated cycles. That is, does there exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph (with lists) either has $k$ disjoint frustrated cycles, or there exists a subsetset of vertices $X$, of vertices with size at most $f(k)$, such that $G -X$ contains no frustrated cycles.

The answer isErdős and Pósa proved that no such function exists. This follows from the fact thatErdős–Pósa property holds for the class of all cycles. However, the Erdős–Pósa property does notnot hold for the class of odd cycles cycles. If From this, it follows that the Erdős–Pósa property does not hold for frustrated cycles. This is because if each list consists of the same two colours, then every odd cycle is athe frustated cyclecycles are precisely the odd cycles.

It sounds like you are asking if the Erdős–Pósa property holds for frustrated cycles. That is, does there exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph (with lists) either has $k$ disjoint frustrated cycles, or there exists a subset $X$ of vertices with size at most $f(k)$, such that $G -X$ contains no frustrated cycles.

The answer is that no such function exists. This follows from the fact that the Erdős–Pósa property does not hold for odd cycles. If each list consists of the same two colours, then every odd cycle is a frustated cycle.

It sounds like you are asking if the Erdős–Pósa property holds for frustrated cycles. That is, does there exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph (with lists) either has $k$ disjoint frustrated cycles, or a set of vertices $X$, of size at most $f(k)$, such that $G -X$ contains no frustrated cycles.

Erdős and Pósa proved that the Erdős–Pósa property holds for the class of all cycles. However, the Erdős–Pósa property does not hold for the class of odd cycles. From this, it follows that the Erdős–Pósa property does not hold for frustrated cycles. This is because if each list consists of the same two colours, then the frustated cycles are precisely the odd cycles.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

It sounds like you are asking if the Erdős–Pósa property holds for frustrated cycles. That is, does there exists a function $f: \mathbb{N} \to \mathbb{N}$, such that every graph (with lists) either has $k$ disjoint frustrated cycles, or there exists a subset $X$ of vertices with size at most $f(k)$, such that $G -X$ contains no frustrated cycles.

The answer is that no such function exists. This follows from the fact that the Erdős–Pósa property does not hold for odd cycles. If each list consists of the same two colours, then every odd cycle is a frustated cycle.