{
  "id": "2211.13931",
  "version": "v1",
  "published": "2022-11-25T06:57:38.000Z",
  "updated": "2022-11-25T06:57:38.000Z",
  "title": "Transitivity on subclasses of chordal graphs",
  "authors": [
    "Subhabrata Paul",
    "Kamal Santra"
  ],
  "comment": "arXiv admin note: text overlap with arXiv:2204.13148",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $G=(V, E)$ be a graph, where $V$ and $E$ are the vertex and edge sets, respectively. For two disjoint subsets $A$ and $B$ of $V$, we say $A$ \\textit{dominates} $B$ if every vertex of $B$ is adjacent to at least one vertex of $A$ in $G$. A vertex partition $\\pi = \\{V_1, V_2, \\ldots, V_k\\}$ of $G$ is called a \\emph{transitive $k$-partition} if $V_i$ dominates $V_j$ for all $i,j$, where $1\\leq i<j\\leq k$. The maximum integer $k$ for which the above partition exists is called \\emph{transitivity} of $G$ and it is denoted by $Tr(G)$. The \\textsc{Maximum Transitivity Problem} is to find a transitive partition of a given graph with the maximum number of partitions. It was known that the decision version of \\textsc{Maximum Transitivity Problem} is NP-complete for chordal graphs [Iterated colorings of graphs, \\emph{Discrete Mathematics}, 278, 2004]. In this paper, we first prove that this problem can be solved in linear time for \\emph{split graphs} and for the \\emph{complement of bipartite chain graphs}, two subclasses of chordal graphs. We also discuss Nordhaus-Gaddum type relations for transitivity and provide counterexamples for an open problem posed by J. T. Hedetniemi and S. T. Hedetniemi [The transitivity of a graph, \\emph{J. Combin. Math. Combin. Comput}, 104, 2018]. Finally, we characterize transitively critical graphs having fixed transitivity.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-25T06:57:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "chordal graphs",
      "subclasses",
      "transitivity problem",
      "bipartite chain graphs",
      "nordhaus-gaddum type relations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}