“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 17631
School of Mathematics
  Title:   A Hall-type theorem with algorithmic consequences in planar graphs
  Author(s):  Hossein Jowhari (Joint with E. Ghorbani)
  Status:   Published
  Journal: Discrete Math.
  Vol.:  347
  Year:  2024
  Pages:   113892
  Supported by:  IPM
Given a graph G =(V, E), for a vertex set Sâ??V, let N(S) denote the set of vertices in V that have a neighbor in S. Extending the concept of binding number of graphs by Woodall (1973), for a vertex set Xâ??V, we define the binding number of X, denoted by bind(X), as the maximum number such that for every Sâ??X where N(S) != V(G) it holds that |N(S)| â?¥b|S|. Given this definition, we prove that if a graph V(G) contains a subset X with bind(X) =1/k where k is an integer, then G possesses a matching of size at least |X|/(k +1). Using this statement, we derive tight bounds for the estimators of the matching size in planar graphs. These estimators are previously used in designing sublinear space algorithms for approximating the matching size in the data stream model of computation. In particular, we show that the number of locally superior vertices is a 3factor approximation of the matching size in planar graphs. The previous analysis by Jowhari (2023) proved a 3.5approximation factor. As another application, we show a simple variant of an estimator by Esfandiari et al. (2015) achieves 3factor approximation of the matching size in planar graphs. Namely, let s be the number of edges with both endpoints having degree at most 2and let h be the number of vertices with degree at least 3. We prove that when the graph is planar, the size of matching is at least (s +h)/3. This result generalizes a known fact that every planar graph on n vertices with minimum degree 3has a matching of size at least n/3.

Download TeX format
back to top
scroll left or right