Displaying similar documents to “Coloring digraphs by iterated antichains”

Ramseyan properties of graphs.

DeLaVina, Ermelinda, Fajtlowicz, Siemion (1996)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Niche Hypergraphs

Christian Garske, Martin Sonntag, Hanns-Martin Teichert (2016)

Discussiones Mathematicae Graph Theory

Similarity:

If D = (V,A) is a digraph, its niche hypergraph NH(D) = (V, E) has the edge set ℇ = {e ⊆ V | |e| ≥ 2 ∧ ∃ v ∈ V : e = N−D(v) ∨ e = N+D(v)}. Niche hypergraphs generalize the well-known niche graphs (see [11]) and are closely related to competition hypergraphs (see [40]) as well as double competition hypergraphs (see [33]). We present several properties of niche hypergraphs of acyclic digraphs.

K3-Worm Colorings of Graphs: Lower Chromatic Number and Gaps in the Chromatic Spectrum

Csilla Bujtás, Zsolt Tuza (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A K3-WORM coloring of a graph G is an assignment of colors to the vertices in such a way that the vertices of each K3-subgraph of G get precisely two colors. We study graphs G which admit at least one such coloring. We disprove a conjecture of Goddard et al. [Congr. Numer. 219 (2014) 161-173] by proving that for every integer k ≥ 3 there exists a K3-WORM-colorable graph in which the minimum number of colors is exactly k. There also exist K3-WORM colorable graphs which have a K3-WORM...

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...

Equitable Colorings Of Corona Multiproducts Of Graphs

Hanna Furmánczyk, Marek Kubale, Vahan V. Mkrtchyan (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts...