Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Induced subgraph isomorphism problem (view), Maximum common induced subgraph (view)

searching for Induced subgraph 20 found (150 total)

Dissociation number (244 words) [view diff] exact match in snippet view article find links to article

{\displaystyle S} of the vertices of a graph G {\displaystyle G} , so that the induced subgraph G [ S ] {\displaystyle G[S]} has maximum degree k {\displaystyle k}

Factor-critical graph (1,792 words) [view diff] exact match in snippet view article find links to article

(or hypomatchable graph) is a graph with n vertices in which every induced subgraph of n − 1 vertices has a perfect matching. (A perfect matching in a

Graph sandwich problem (537 words) [view diff] exact match in snippet view article find links to article

Silva, Murilo V.G.; Teixeira, Rafael B. (2011), "On the forbidden induced subgraph sandwich problem", Discrete Applied Mathematics, 159 (16): 1717–1725

Signed graph (3,249 words) [view diff] exact match in snippet view article find links to article

in balance. Equivalently, one wants the largest order of a balanced induced subgraph of Σ. Three fundamental questions about a signed graph are: Is it balanced

List of conjectures by Paul Erdős (1,438 words) [view diff] exact match in snippet view article find links to article

Erdős–Hajnal conjecture that in a family of graphs defined by an excluded induced subgraph, every graph has either a large clique or a large independent set.

Möbius–Kantor graph (1,528 words) [view diff] exact match in snippet view article find links to article

crossing edges. The Möbius–Kantor graph also occurs many times as an induced subgraph of the Hoffman–Singleton graph. Each of these instances is in fact

Circular-arc graph (866 words) [view diff] exact match in snippet view article find links to article

algorithm returns a certificate of this fact in the form of a forbidden induced subgraph. They also gave an O(n) time algorithm for determining whether a given

Line graph of a hypergraph (1,201 words) [view diff] exact match in snippet view article find links to article

existence of a polynomial recognition or the possibility of a forbidden induced subgraph characterization similar to Beineke's of line graphs of graphs. There

Julia Böttcher (288 words) [view diff] exact match in snippet view article find links to article

relating the degree and the chromatic number of graphs with a forbidden induced subgraph. She was an invited speaker at the 2022 (virtual) International Congress

List of PSPACE-complete problems (1,807 words) [view diff] exact match in snippet view article find links to article

clique-forming game: two players alternately select vertices and the induced subgraph must be an independent set (resp. clique). The last to play wins. Nondeterministic

Two-graph (1,591 words) [view diff] exact match in snippet view article find links to article

simple graph G = (V,E), the set of triples of the vertex set V whose induced subgraph has an odd number of edges forms a two-graph on the set V. Every two-graph

Cuckoo hashing (2,563 words) [view diff] exact match in snippet view article find links to article

at most one cycle in each of its connected components. Any vertex-induced subgraph with more edges than vertices corresponds to a set of keys for which

Graph minor (4,046 words) [view diff] exact match in snippet view article find links to article

called an induced minor of a graph G if it can be obtained from an induced subgraph of G by contracting edges. Otherwise, G is said to be H-induced minor-free

Scale-free network (6,401 words) [view diff] exact match in snippet view article find links to article

nodes and power-law exponent γ > 3 {\displaystyle \gamma >3} , the induced subgraph constructed by vertices with degrees larger than log ⁡ n × log ∗ ⁡

Incidence coloring (3,817 words) [view diff] exact match in snippet view article find links to article

1 {\displaystyle G_{1}} (resp. G 2 {\displaystyle G_{2}} ) be the induced subgraph on vertex v and vertices of H 1 {\displaystyle H_{1}} (resp. H 2 {\displaystyle

Chromatic symmetric function (2,063 words) [view diff] exact match in snippet view article find links to article

parts are the vertex sizes of the connected components of the edge-induced subgraph of G {\displaystyle G} specified by S {\displaystyle S} . The chromatic

List of unsolved problems in mathematics (19,551 words) [view diff] exact match in snippet view article find links to article

conjecture on large cliques or independent sets in graphs with a forbidden induced subgraph The linear arboricity conjecture on decomposing graphs into disjoint

Network motif (10,371 words) [view diff] case mismatch in snippet view article find links to article

(used in CytoKavosh) Both Induced G-Tries Both Induced PGD Undirected Induced Subgraph-Centric FPF (Mavisto) Both Induced NeMoFinder Undirected Induced Grochow–Kellis

Hall-type theorems for hypergraphs (6,498 words) [view diff] exact match in snippet view article find links to article

(note that Vy is a subset of V). Then, for every subset Y0 of Y, the induced subgraph G [ V Y 0 ] {\displaystyle G[V_{Y_{0}}]} contains a clique for every

Decomposition method (constraint satisfaction) (5,804 words) [view diff] exact match in snippet view article

biconnected component of a graph is a maximal set of its nodes whose induced subgraph is connected and does not have any separating vertex. It is known from