{
  "id": "2403.08465",
  "version": "v1",
  "published": "2024-03-13T12:28:17.000Z",
  "updated": "2024-03-13T12:28:17.000Z",
  "title": "New Invariants for Partitioning a Graph into 2-connected Subgraphs",
  "authors": [
    "Michitaka Furuya",
    "Masaki Kashima",
    "Katsuhiro Ota"
  ],
  "comment": "14 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A vertex partition in which every part induces a 2-connected subgraph is called a 2-proper partition. This concept was introduced by Ferrara et al. in 2013, and Borozan et al. gave the best possible minimum degree condition for the existence of a 2-proper partition in 2016. Later, in 2022, Chen et al. extended the result by showing a minimum degree sum condition for the existence of 2-proper partition. In this paper, we introduce two new invariants of graph, denoted by $\\sigma^*(G)$ and $\\alpha^*(G)$. These two invariants are defined from degree sum on all independent sets with some property. We prove that if a graph $G$ satisfies $\\sigma^*(G)\\geq |V(G)|$, then with some exceptions, $G$ has a 2-proper partition with at most $\\alpha^*(G)$ parts. This result is best possible, and implies both of the results by Borozan et al. and by Chen et al.. Moreover, as a corollary of our result, we give a minimum degree product condition for the existence of a 2-proper partition.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-13T12:28:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07"
    ],
    "keywords": [
      "invariants",
      "minimum degree sum condition",
      "minimum degree product condition",
      "minimum degree condition",
      "part induces"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}