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 …
Calendar of Events
|
Sunday
|
Monday
|
Tuesday
|
Wednesday
|
Thursday
|
Friday
|
Saturday
|
|---|---|---|---|---|---|---|
|
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 $f : \mathbb{N} \to \mathbb{N}$ such that for every function $g : \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ with $g(1)=1$ and $g \ge f$, there is a hereditary class of graphs $\mathcal{G}$ such that for each $\omega \in \mathbb{N}$, the maximum chromatic number of a graph in $\mathcal{G}$ with … |
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 $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$, every connected $n$-vertex graph of maximum degree at most $\Delta$ has … |
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 $3$-connected graph $G$ has an edge $e$ such that $G \setminus e$ or $G / e$ is simple $3$-connected, unless $G$ is isomorphic to a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless … |
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 $\mathbb F$, the list contains only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded … |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|

