Results 41 to 50 of about 438 (125)
, 2019 Cographs--defined most simply as complete graphs with colored lines--both dualize and generalize ordinary graphs, and promise a comparably wide range of applications. This article introduces them by examples, catalogues, and elementary properties. Any finite cograph may be realized in several ways, including inner products, polynomials, geometrically ...
openaire +2 more sources
The pathwidth and treewidth of cographs [PDF]
SIAM Journal on Discrete Mathematics, 1990 Summary: It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.
Bodlaender, Hans, Möhring, Rolf H.
openaire +2 more sources
A linear algorithm for obtaining the Laplacian eigenvalues of a cograph [PDF]
, 2023 Guantao Chen, Fernando Tura
openalex +1 more source
Graphic splitting of cographic matroids
Discussiones Mathematicae Graph Theory, 2015 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +3 more sources
Cograph generation with linear delay [PDF]
Theoretical Computer Science, 2018 Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with $n$ vertices, based on the generation of cotrees. The delay of our algorithm (time spent between two consecutive outputs) is $O(n)$.
Jones, Átila A. +2 more
openaire +2 more sources
Combinatorial Logarithm and Point-Determining Cographs [PDF]
The Electronic Journal of Combinatorics, 2012 We obtain the reduced form of the “combinatorial logarithm” Ω by looking at bijections related to connected point-determining cographs and connected co-point-determining graphs.
openaire +2 more sources
Weighted and locally bounded list-colorings in split graphs, cographs, and partial k-trees [PDF]
, 2019 Cédric Bentz
openalex +2 more sources
Acyclic and star colorings of cographs
Discrete Applied Mathematics, 2011 An \emph{acyclic coloring} of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees. The more restricted notion of \emph{star coloring} requires that the union of any two color classes induces a disjoint collection of stars.
openaire +3 more sources
Asymptotic enumeration of cographs
Electronic Notes in Discrete Mathematics, 2001 Abstract Abstract We consider here labelled and unlabelled cographs, i.e., graphs without induced P4, whose applications are important in computer science and logic, because of their representation by means of parse trees. After a new (analytical) approach for obtaining generating functions associated to parse trees, we solve the open problem of ...
Vlady Ravelomanana, Loÿs Thimonier
openaire +1 more source
Hierarchical Colorings of Cographs
, 2019 Cographs are exactly hereditarily well-colored graphs, i.e., the graphs for which a greedy coloring of every induced subgraph uses only the minimally necessary number of colors $ (G)$. In recent work on reciprocal best match graphs so-called hierarchically coloring play an important role.
Valdivia, D. I. +4 more
openaire +2 more sources