Results 1 to 10 of about 3,722 (68)
H-kernels by walks in H-colored digraphs and the color-class digraph
AKCE International Journal of Graphs and Combinatorics, 2016 Let H be a digraph possibly with loops and D a finite digraph without loops whose arcs are colored with the vertices of H (D is an H-colored digraph). V(D) and A(D) will denote the sets of vertices and arcs of D respectively.
Hortensia Galeana-Sánchez +1 more
doaj +3 more sources
H-Kernels in Unions of H-Colored Quasi-Transitive Digraphs
Discussiones Mathematicae Graph Theory, 2021 Let H be a digraph (possibly with loops) and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). For an arc (x, y) of D, its color is denoted by c(x, y). A directed path W = (v0, . .
Campero-Alonzo José Manuel +1 more
doaj +3 more sources
New Bounds for the Dichromatic Number of a Digraph [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 The chromatic number of a graph $G$, denoted by $\chi(G)$, is the minimum $k$ such that $G$ admits a $k$-coloring of its vertex set in such a way that each color class is an independent set (a set of pairwise non-adjacent vertices).
Narda Cordero-Michel +1 more
doaj +3 more sources
Kernels by monochromatic paths and the color-class digraph
Discussiones Mathematicae Graph Theory, 2011 An m-coloured digraph is a digraph whose arcs are coloured with m colors. A directed path is monochromatic when its arcs are coloured alike. A set S ⊆ V (D) is a kernel by monochromatic paths whenever the two following conditions hold: 1. For any x, y ∈ S, x 6= y, there is no monochromatic directed path between them. 2.
Hortensia Galeana‐Sánchez
openaire +3 more sources
The conjugacy problem for automorphism groups of countable homogeneous structures [PDF]
, 2016 We consider the conjugacy problem for the automorphism groups of a number of countable homogeneous structures.
Coskey, Samuel, Ellis, Paul
core +3 more sources
Kernels by Monochromatic Paths and Color-Perfect Digraphs
Discussiones Mathematicae Graph Theory, 2016 For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no
Galeana-Śanchez Hortensia +1 more
doaj +1 more source
Nondeterministic graph property testing [PDF]
, 2012 A property of finite graphs is called nondeterministically testable if it has a "certificate" such that once the certificate is specified, its correctness can be verified by random local testing. In this paper we study certificates that consist of one or
Fischer +3 more
core +1 more source
Oriented coloring on recursively defined digraphs
, 2019 Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph G=(V,A)
Gurski, Frank +2 more
core +1 more source
Inverse monoids of partial graph automorphisms
, 2020 A partial automorphism of a finite graph is an isomorphism between its vertex induced subgraphs. The set of all partial automorphisms of a given finite graph forms an inverse monoid under composition (of partial maps). We describe the algebraic structure
Jajcay, Robert +3 more
core +1 more source
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
, 2017 We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a $d$-degenerate graph $G$ and an integer $k$, outputs an independent set $Y$, such that for ...
Lokshtanov, Daniel +4 more
core +1 more source