Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by …
Seminars and Colloquiums
Calendar of Events
S
Sun
|
M
Mon
|
T
Tue
|
W
Wed
|
T
Thu
|
F
Fri
|
S
Sat
|
---|---|---|---|---|---|---|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
1 event,
-
Pascal Gollin, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
Pascal Gollin, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
|
0 events,
|
1 event,
-
We prove that there is a function |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
1 event,
-
An independent dominating set of a graph, also known as a maximal independent set, is a set |
0 events,
|
0 events,
|
1 event,
-
A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G), and such that uv is an edge if and only if the distance between u and v in T is at most k. The graph classes of k-leaf powers have several applications in computational biology, but recognizing … |
0 events,
|
0 events,
|
1 event,
-
Tutte (1961) proved that every simple |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
1 event,
-
Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|