{
  "id": "2305.03585",
  "version": "v1",
  "published": "2023-05-05T14:44:33.000Z",
  "updated": "2023-05-05T14:44:33.000Z",
  "title": "Quorum colorings of maximum cardinality in linear time for a subclass of perfect trees",
  "authors": [
    "Rafik Sahbi",
    "Wissam Boumalha",
    "Asmaa Issad"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A partition $\\pi=\\{V_{1},V_{2},...,V_{k}\\}$ of the vertex set $V$ of a graph $G$ into $k$ color classes $V_{i}$, with $1\\leq i\\leq k$ is called a quorum coloring of $G$ if for every vertex $v\\in V$, at least half of the vertices in the closed neighborhood $N[v]$ of $v$ have the same color as $v$. The maximum cardinality of a quorum coloring of $G$ is called the quorum coloring number of $G$ and is denoted by $\\psi_{q}(G)$. A quorum coloring of order $\\psi_{q}(G)$ is a $\\psi_{q}$-coloring. The determination of the quorum coloring number or design a linear-time algorithm computing it in a perfect $N$-ary tree has been posed recently as an open problem by Sahbi. In this paper, we answer this problem by designing a linear-time algorithm for finding both a $\\psi_{q}$-coloring and the quorum coloring number for every perfect tree whose the vertices at the same depth have the same degree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-05-05T14:44:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C69"
    ],
    "keywords": [
      "maximum cardinality",
      "perfect tree",
      "quorum coloring number",
      "linear time",
      "linear-time algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}