Results 81 to 90 of about 1,967 (126)
Data Reduction for Graph Coloring Problems
, 2013 This paper studies the kernelization complexity of graph coloring problems with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring
Bart M.P. Jansen +30 more
core +1 more source
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
Clique cycle-transversals in distance-hereditary graphs
, 2013 A cycle-transversal of a graph G is a subset T of V(G) such that T intersects every cycle of G. A clique cycle-transversal, or cct for short, is a cycle-transversal which is a clique.
Brandstädt, Andreas +3 more
core +1 more source
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
On Complexities of Minus Domination
, 2013 A function f: V \rightarrow \{-1,0,1\} is a minus-domination function of a graph G=(V,E) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f(x) over all vertices x \in V.
Faria, Luérbio +5 more
core +1 more source
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
Vizing's conjecture for cographs
, 2016 We show that if $G$ is a cograph, that is $P_4$-free, then for any graph $H$, $ (G\square H)\geq (G) (H)$. By the characterization of cographs as a finite sequence of unions and joins of $K_1$, this result easily follows from that of Bartsalkin and German. However, the techniques used are new and may be useful to prove other results.
openaire +2 more sources