Results 41 to 50 of about 1,967 (126)
Partitions of Graphs into Cographs
Electronic Notes in Discrete Mathematics, 2002 A cograph is a graph that can be constructed by a single vertex using complementation and disjoint union operations. Equivalently, cographs are exactly those graphs which do not contain an induced path \(P_4\) with four vertices and three edges. The \(c\)-chromatic number \(c(G)\) of a graph \(G\) is the minimum number \(k\) such that the vertex set of
Gimbel, John, Nešetřil, Jaroslav
openaire +2 more sources
Removing Twins in Graphs to Break Symmetries
Mathematics, 2019 Determining vertex subsets are known tools to provide information about automorphism groups of graphs and, consequently about symmetries of graphs. In this paper, we provide both lower and upper bounds of the minimum size of such vertex subsets, called ...
Antonio González, María Luz Puertas
doaj +1 more source
Characterizing –partitionable Cographs
Electronic Notes in Discrete Mathematics, 2005 Abstract We consider the problem of partitioning a graph into k independent sets and l cliques, known as the ( k , l ) -partition problem, which was introduced by Brandstadt in [A. Bransdstadt, Partitions of graphs into one or two independent sets and cliques, Discrete Mathematics 152 (1996) 47–54], and generalized by Feder et al.
Raquel de Souza Francisco +2 more
openaire +1 more source
On Certain Eigenspaces of Cographs [PDF]
The Electronic Journal of Combinatorics, 2008 For every cograph there exist bases of the eigenspaces for the eigenvalues $0$ and $-1$ that consist only of vectors with entries from $\{0, 1, -1\}$, a property also exhibited by other graph classes. Moreover, the multiplicities of the eigenvalues $0$ and $-1$ of a cograph can be determined by counting certain vertices of the associated cotree.
openaire +2 more sources
Algorithmic aspects of switch cographs
Discrete Applied Mathematics, 2016 This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structure which has a unique linear-sized decomposition tree. We derive an O(n^2) decomposition algorithm and we take advantage of the involution modular decomposition tree to state several algorithmic results.
Cohen-Addad, Vincent +2 more
openaire +3 more sources
On retracts, absolute retracts, and folds in cographs [PDF]
, 2013 Let G and H be two cographs. We show that the problem to determine whether H is a retract of G is NP-complete. We show that this problem is fixed-parameter tractable when parameterized by the size of H. When restricted to the class of threshold graphs or
A. Máté +16 more
core +1 more source
Confining the robber on cographs
Contributions to Discrete Mathematics, 2023 In a game of Cops and Robbers on graphs, usually the cops' objective is to capture the robber---a situation which the robber wants to avoid invariably. In this paper, we begin with introducing the notions of trapping and confining the robber and discussing their relations with capturing the robber.
openaire +3 more sources
Convex Independence in Permutation Graphs
, 2016 A set C of vertices of a graph is P_3-convex if every vertex outside C has at most one neighbor in C. The convex hull \sigma(A) of a set A is the smallest P_3-convex set that contains A.
B Courcelle +11 more
core +1 more source
, 2010 Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis.
A. Cournier +17 more
core +1 more source
b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs [PDF]
, 2013 A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by \chi_b(G), is the maximum number t such that G admits a b-coloring ...
C Berge +12 more
core +7 more sources