Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Generating subgraphs in chordal graphs   A graph $G$ is well-covered if all its maximal independent sets are of the
same cardinality. Assume that a weight function $w$ is defined on its vertices.
Then $G$ is $w$-well-covered if all maximal independent sets are of the same
weight. For every graph $G$, the set of weight functions $w$ such that $G$ is
$w$-well-covered is a vector space, denoted $WCW(G)$. Let $B$ be a complete
bipartite induced subgraph of $G$ on vertex sets of bipartition $B_{X}$ and
$B_{Y}$. Then $B$ is generating if there exists an independent set $S$ such
that $S \cup B_{X}$ and $S \cup B_{Y}$ are both maximal independent sets of
$G$. In the restricted case that a generating subgraph $B$ is isomorphic to
$K_{1,1}$, the unique edge in $B$ is called a relating edge. Generating
subgraphs play an important role in finding $WCW(G)$. Deciding whether an input
graph $G$ is well-covered is co-NP-complete. Hence, finding $WCW(G)$ is
co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore,
deciding whether a subgraph is generating is NP-complete as well. A graph is
chordal if every induced cycle is a triangle. It is known that finding $WCW(G)$
can be done polynomially in the restricted case that $G$ is chordal. Thus
recognizing well-covered chordal graphs is a polynomial problem. We present a
polynomial algorithm for recognizing relating edges and generating subgraphs in
chordal graphs.

0
The categories of this paper are: hep-ph
9
The categories of this paper are: nlin
5
The categories of this paper are: gr-qc
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
26
The categories of this paper are: bayes-an
11
The categories of this paper are: hep-lat
8
The categories of this paper are: hep-ex
16
The categories of this paper are: stat
37
The categories of this paper are: supr-con
4
The categories of this paper are: cond-mat
29
The categories of this paper are: funct-an
30
The categories of this paper are: q-alg
28
The categories of this paper are: alg-geom
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex