Results 281 to 290 of about 142,988 (312)
Some of the next articles are maybe not open access.
Journal of Graph Theory, 2006
AbstractIn this article we introduce certain classes of graphs that generalize ϕ‐tolerance chain graphs. In a rank‐tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if
Martin Charles Golumbic +1 more
openaire +2 more sources
AbstractIn this article we introduce certain classes of graphs that generalize ϕ‐tolerance chain graphs. In a rank‐tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if
Martin Charles Golumbic +1 more
openaire +2 more sources
SIAM Journal on Algebraic Discrete Methods, 1982
Let P be a simply connected polyomino. Let $G( P )$ be the graph whose vertices are the maximal rectangles in P, two such vertices being adjacent if the corresponding rectangles have nontrivial intersection. In this paper we show that $G ( P )$ is perfect. This solves a problem posed by Berge et al.
openaire +2 more sources
Let P be a simply connected polyomino. Let $G( P )$ be the graph whose vertices are the maximal rectangles in P, two such vertices being adjacent if the corresponding rectangles have nontrivial intersection. In this paper we show that $G ( P )$ is perfect. This solves a problem posed by Berge et al.
openaire +2 more sources
Intersection Dimensions of Graph Classes
Graphs and Combinatorics, 1994``The intersection dimension of a graph \(G\) with respect to a class \(A\) of graphs is the minimum \(k\) such that \(G\) is the intersection of at most \(k\) graphs on vertex set \(V(G)\) each of which belongs to \(A\). We consider the question when the intersection dimension of a certain family of graphs is bounded or unbounded.'' If \(A\) is ...
Jan Kratochvíl, Zsolt Tuza
openaire +2 more sources
Properties of Classes of Random Graphs
Combinatorics, Probability and Computing, 1994In [11] it is shown that the theory of almost all graphs is first-order complete. Furthermore, in [3] a collection of first-order axioms are given from which any first-order property or its negation can be deduced. Here we show that almost all Steinhaus graphs satisfy the axioms of almost all graphs and conclude that a first-order property is true for ...
Neal Brand, Steve Jackson 0001
openaire +1 more source
2018
This edited volume offers a detailed account on the theory of directed graphs from the perspective of important classes of digraphs, with each chapter written by experts on the topic.Outlining fundamental discoveries and new results obtained over recent years, this book provides a comprehensive overview of the latest research in the field.
openaire +2 more sources
This edited volume offers a detailed account on the theory of directed graphs from the perspective of important classes of digraphs, with each chapter written by experts on the topic.Outlining fundamental discoveries and new results obtained over recent years, this book provides a comprehensive overview of the latest research in the field.
openaire +2 more sources
A class of upper‐embeddable graphs
Journal of Graph Theory, 1979AbstractIn this paper, we prove the following result: Every graph obtained by connecting (with any number of edges) two vertex‐disjoint upper‐embeddable graphs graphs with even Betti number is upper‐embeddable.
François Jaeger +2 more
openaire +1 more source
Class‐reconstruction of total graphs
Journal of Graph Theory, 1987AbstractIt is shown that given any vertex‐deleted total graph, every reconstruction into a total graph by the addition of a vertex yields the original total graph. The proof indicates how the reconstruction can be done.
David W. Bange +2 more
openaire +2 more sources
The Parallel Recognition of Classes of Graphs
IEEE Transactions on Computers, 1980Parallel cellular algorithms for recognizing adjacency and incidence matrices of several classes of graphs are given. These classes include cubic graphs, complete graphs, connected graphs, and trees.
openaire +1 more source
Boundary Classes of Planar Graphs
Combinatorics, Probability and Computing, 2008We analyse classes of planar graphs with respect to various properties such as polynomial-time solvability of thedominating setproblem or boundedness of the tree-width. A helpful tool to address this question is the notion of boundary classes. The main result of the paper is that for many important properties there are exactly two boundary classes of ...
openaire +2 more sources
Classes of Graphs that Are Not Vertex Ramsey
SIAM Journal on Discrete Mathematics, 1997Summary: \textit{N. Sauer} [Combinatorics, Paul Erdős is eighty. Vol. 1, 361-377 (1993; Zbl 0795.05104)] has conjectured that for any tree \(T\) and any clique \(K\), the class \(\text{Forb} (T, K)\) of graphs that induces neither \(T\) nor \(K\) is not vertex Ramsey.
openaire +2 more sources