Results 91 to 100 of about 10,864 (212)
On Hereditary Helly classes of graphs
Discrete Mathematics & Theoretical Computer Science, 2008 In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively.
Marina Groshaus, Jayme Luiz Szwarcfiter
doaj
Subgraphs and Colourability of Locatable Graphs [PDF]
, 2014 We study a game of pursuit and evasion introduced by Seager in 2012, in which a cop searches the robber from outside the graph, using distance queries. A graph on which the cop wins is called locatable.
Johnson, Richard A. B., Koch, Sebastian
core
Complexity Framework for Forbidden Subgraphs
, 2022 For any finite set H={H1,…,Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,…,Hp as a subgraph. Similar to known meta-classifications for the minor and topological minor relations, we give a meta-classification for the subgraph relation.
Johnson, Matthew S. +6 more
openaire +2 more sources
$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses [PDF]
Discrete Mathematics & Theoretical Computer ScienceA graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs.
Fernando Esteban Contreras-Mendoza +1 more
doaj +1 more source
Random multilinear maps and the Erdős box problem
Discrete Analysis, 2021 Random multilinear maps and the Erdős box problem, Discrete Analysis 2021:17, 8 pp. A major theme in extremal combinatorics is determining the maximum number of edges that a graph or hypergraph can have if it does not contain a certain fixed graph or ...
David Conlon +2 more
doaj +1 more source
Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult [PDF]
, 2003 We consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs.
Broersma, H.J. +3 more
core +2 more sources
Embedding and NP-complete Problems for Some Equitable Labelings
Journal of Applied Computer Science & Mathematics, 2014 A cordial labeling or an equitable labeling is a weaker version of Graceful and Harmonious labelings. At present many variants of equitable labeling are available.
Samir K. VAIDYA, Chirag M. BARASARA
doaj
Small clique number graphs with three trivial critical ideals
Special Matrices, 2018 The critical ideals of a graph are the determinantal ideals of the generalized Laplacian matrix associated to a graph. Previously, they have been used in the understanding and characterizing of the graphs with critical group with few invariant factors ...
Alfaro Carlos A., Valencia Carlos E.
doaj +1 more source
Relative timing information and orthology in evolutionary scenarios. [PDF]
Algorithms Mol Biol, 2023 Schaller D +5 more
europepmc +1 more source
Density theorems for bipartite graphs and related Ramsey-type results
, 2007 In this paper, we present several density-type theorems which show how to find a copy of a sparse bipartite graph in a graph of positive density.
Fox, Jacob, Sudakov, Benny
core +4 more sources