Results 71 to 80 of about 10,864 (212)
The number of graphs with large forbidden subgraphs
European Journal of Combinatorics, 2010 6 ...
Vladimir Nikiforov, Béla Bollobás
openaire +3 more sources
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth [PDF]
Information and Computation, 2014 We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph $H$ and an input graph $G$, the task is to find a set $X \subseteq V(G)$ of minimum size that hits all subgraphs of $G$ isomorphic to $H$. In the colorful variant of the problem, each vertex of $G$ is precolored with some color from $V(H)$ and we ...
Cygan, Marek +3 more
openaire +6 more sources
Rainbow vertex-connection and forbidden subgraphs
Discussiones Mathematicae Graph Theory, 2018 11 ...
Xueliang Li, Wenjing Li, Jingshu Zhang
openaire +4 more sources
Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
, 2014 In this paper, we address the problem of enumerating all induced subtrees in an input k-degenerate graph, where an induced subtree is an acyclic and connected induced subgraph.
A Shioura +7 more
core +1 more source
Some Variations of Perfect Graphs
Discussiones Mathematicae Graph Theory, 2016 We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively.
Dettlaff Magda +3 more
doaj +1 more source
Graph Classes Generated by Mycielskians
Discussiones Mathematicae Graph Theory, 2020 In this paper we use the classical notion of weak Mycielskian M′(G) of a graph G and the following sequence: M′0(G) = G, M′1(G) = M′(G), and M′n(G) = M′(M′n−1(G)), to show that if G is a complete graph of order p, then the above sequence is a generator ...
Borowiecki Mieczys law +3 more
doaj +1 more source
Characterising and recognising game-perfect graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 Consider a vertex colouring game played on a simple graph with $k$ permissible colours. Two players, a maker and a breaker, take turns to colour an uncoloured vertex such that adjacent vertices receive different colours.
Dominique Andres, Edwin Lock
doaj +1 more source
Forbidden subgraphs and the König–Egerváry property
Discrete Applied Mathematics, 2013 The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the Konig-Egervary property if its matching number equals its transversal number.
Luciano N. Grippo +8 more
openaire +8 more sources
The graph grabbing game on {0,1}-weighted graphs
Results in Applied Mathematics, 2019 The graph grabbing game is a two-player game on a weighted connected graph in which two players, Alice and Bob, alternatively remove non-cut vertices one by one to gain the weights on them.
Soogang Eoh, Jihoon Choi
doaj
Forbidden Pairs and (k,m)-Pancyclicity
Discussiones Mathematicae Graph Theory, 2017 A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}.
Crane Charles Brian
doaj +1 more source