Results 261 to 270 of about 3,844 (297)

Vertex partitions of graphs into cographs and stars

J. Graph Theory, 2014
Summary: A cograph is a graph that contains no path on four vertices as an induced subgraph. A cograph \(k\)-partition of a graph \(G\) = (\(V,E\)) is a vertex partition of \(G\) into \(k\) sets \(V_{1}, \ldots , V_{k} \subset V\) so that the graph induced by \(V_{i}\) is a cograph for \(1 \leq i \leq k\). \textit{J. Gimbel} and \textit{J.
Paul Dorbec, Mickaël Montassier, Pascal Ochem   +2 more
openaire   +2 more sources

Some of the next articles are maybe not open access.

Related searches:

Vertex partitions and maximum degenerate subgraphs

Journal of Graph Theory, 2007
AbstractLet G be a graph with maximum degree d≥ 3 and ω(G)≤ d, where ω(G) is the clique number of the graph G. Let p1 and p2 be two positive integers such that d = p1 + p2. In this work, we prove that G has a vertex partition S1, S2 such that G[S1] is a maximum order (p1‐1)‐degenerate subgraph of G and G[S2] is a (p2‐1)‐degenerate subgraph, where G[Si]
Martin Matamala
exaly   +2 more sources

Co-2-plex vertex partitions

Journal of Combinatorial Optimization, 2013
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Benjamin Mcclosky, Illya V Hicks
exaly   +2 more sources

Vertex Partitions of K4,4-Minor Free Graphs

Graphs and Combinatorics, 2001
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Leif K Jørgensen
exaly   +4 more sources

Canonical Vertex Partitions

Combinatorics, Probability and Computing, 2003
Let σ be a finite relational signature, let be a set of finite complete relational structures of signature σ, and let be the countable homogeneous relational structure of signature σ which does not embed any of the structures in .When σ consists of at most binary relations and is finite, the vertex partition behaviour of is completely analysed, in ...
openaire   +1 more source

Distant Vertex Partitions of Graphs

Combinatorics, Probability and Computing, 1998
We consider the function χ(Gk), defined to be the smallest number of colours that can colour a graph G in such a way that no vertices of distance at most k receive the same colour. In particular we shall look at how small a value this function can take in terms of the order and diameter of G. We get general bounds for this and tight bounds for
openaire   +2 more sources

Transversals of Vertex Partitions in Graphs

SIAM Journal on Discrete Mathematics, 1990
This paper studies a number of graph-theoretic parameters that are defined by statements of the form: For every partition of the vertex set that satisfies an upper (or lower) bound on the number of elements in each partition class, there is a transveral of the partition that is an independent (or dominating) set.
openaire   +1 more source

Efficient graph automorphism by vertex partitioning

Artificial Intelligence, 1983
We describe a vertex partitioning method and squeeze tree search technique, which can be used to determine the automorphism partition of a graph in polynomial time for all graphs tested, including those which are strongly regular. The vertex partitioning procedure is based on first transforming the graph by the 1-or 2-subdivision transform or the 1-or ...
Fowler, G., Haralick, R., Gray, F. G., Feustel, C., Grinstead, Charles M.   +4 more
openaire   +2 more sources

Computational techniques for vertex partitioning of graphs

Journal of Chemical Information and Computer Sciences, 1990
A powerful vertex-partitioning algorithm is developed and applied for vertex partitioning of graphs of chemical and spectroscopic interest. The codes developed on the basis of these algorithms are tested and compared for performance with other methods based on the Morgan algorithm and the principal eigenvector algorithm based on the Givens-Householder ...
Xiaoyu Liu 0007, Krishnan Balasubramanian, Morton E. Munk   +2 more
openaire   +2 more sources

A rooted-forest partition with uniform vertex demand

Journal of Combinatorial Optimization, 2010
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Naoki Katoh, Shin-ichi Tanigawa
openaire   +1 more source