Displaying similar documents to “Niche Hypergraphs”

Competition hypergraphs of digraphs with certain properties I. Strong connectedness

Martin Sonntag, Hanns-Martin Teichert (2008)

Discussiones Mathematicae Graph Theory

Similarity:

If D = (V,A) is a digraph, its competition hypergraph 𝓒𝓗(D) has the vertex set V and e ⊆ V is an edge of 𝓒𝓗(D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = {w ∈ V|(w,v) ∈ A}. We tackle the problem to minimize the number of strong components in D without changing the competition hypergraph 𝓒𝓗(D). The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [3].

Directed hypergraphs: a tool for researching digraphs and hypergraphs

Hortensia Galeana-Sánchez, Martín Manrique (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we introduce the concept of directed hypergraph. It is a generalisation of the concept of digraph and is closely related with hypergraphs. The basic idea is to take a hypergraph, partition its edges non-trivially (when possible), and give a total order to such partitions. The elements of these partitions are called levels. In order to preserve the structure of the underlying hypergraph, we ask that only vertices which belong to exactly the same edges may be in the...

Coloring digraphs by iterated antichains

Svatopluk Poljak (1991)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We show that the minimum chromatic number of a product of two n -chromatic graphs is either bounded by 9, or tends to infinity. The result is obtained by the study of coloring iterated adjoints of a digraph by iterated antichains of a poset.

Hypergraphs with Pendant Paths are not Chromatically Unique

Ioan Tomescu (2014)

Discussiones Mathematicae Graph Theory

Similarity:

In this note it is shown that every hypergraph containing a pendant path of length at least 2 is not chromatically unique. The same conclusion holds for h-uniform r-quasi linear 3-cycle if r ≥ 2.

Rainbow Connectivity of Cacti and of Some Infinite Digraphs

Jesús Alva-Samos, Juan José Montellano-Ballesteros (2017)

Discussiones Mathematicae Graph Theory

Similarity:

An arc-coloured digraph D = (V,A) is said to be rainbow connected if for every pair {u, v} ⊆ V there is a directed uv-path all whose arcs have different colours and a directed vu-path all whose arcs have different colours. The minimum number of colours required to make the digraph D rainbow connected is called the rainbow connection number of D, denoted rc⃗ (D). A cactus is a digraph where each arc belongs to exactly one directed cycle. In this paper we give sharp upper and lower bounds...

Constrained Colouring and σ-Hypergraphs

Yair Caro, Josef Lauri, Christina Zarb (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A constrained colouring or, more specifically, an (α, β)-colouring of a hypergraph H, is an assignment of colours to its vertices such that no edge of H contains less than α or more than β vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for r-uniform hypergraphs, classical colourings correspond to (2, r)-colourings while an important instance of...

Sharp Upper Bounds for Generalized Edge-Connectivity of Product Graphs

Yuefang Sun (2016)

Discussiones Mathematicae Graph Theory

Similarity:

The generalized k-connectivity κk(G) of a graph G was introduced by Hager in 1985. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λk(G) = min{λ(S) : S ⊆ V (G) and |S| = k}, where λ(S) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . . , Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper, we study the generalized edge- connectivity of product graphs and obtain sharp...

Kernels in edge coloured line digraph

H. Galeana-Sánchez, L. Pastrana Ramírez (1998)

Discussiones Mathematicae Graph Theory

Similarity:

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path (or a directed cycle) is called monochromatic if all of its arcs are coloured alike. A set N ⊆ V(D) is said to be a kernel by monochromatic paths if it satisfies the two following conditions (i) for every pair of different vertices u, v ∈ N there is no monochromatic directed path between them and (ii) for every vertex x ∈ V(D)-N there is a vertex y ∈ N such that there is an...

Pattern hypergraphs.

Dvořák, Zdeněk, Kára, Jan, Král', Daniel, Pangrác, Ondřej (2010)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Sum List Edge Colorings of Graphs

Arnfried Kemnitz, Massimiliano Marangio, Margit Voigt (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f)...

Generalized total colorings of graphs

Mieczysław Borowiecki, Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be additive hereditary properties of graphs. A (P,Q)-total coloring of a simple graph G is a coloring of the vertices V(G) and edges E(G) of G such that for each color i the vertices colored by i induce a subgraph of property P, the edges colored by i induce a subgraph of property Q and incident vertices and edges obtain different colors. In this...

On improper interval edge colourings

Peter Hudák, František Kardoš, Tomáš Madaras, Michaela Vrbjarová (2016)

Czechoslovak Mathematical Journal

Similarity:

We study improper interval edge colourings, defined by the requirement that the edge colours around each vertex form an integer interval. For the corresponding chromatic invariant (being the maximum number of colours in such a colouring), we present upper and lower bounds and discuss their qualities; also, we determine its values and estimates for graphs of various families, like wheels, prisms or complete graphs. The study of this parameter was inspired by the interval colouring, introduced...