An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let denote a class of all such properties. In the paper, we consider H-reducible over properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.
The notion of Cayley color graphs of groups is generalized to inverse semigroups and groupoids. The set of partial automorphisms of the Cayley color graph of an inverse semigroup or a groupoid is isomorphic to the original inverse semigroup or groupoid. The groupoid of color permuting partial automorphisms of the Cayley color graph of a transitive groupoid is isomorphic to the original groupoid.
Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum number of...
Given a graph G = (V,E) and a set Lv of admissible colors for each vertex v ∈ V (termed the list at v), a list coloring of G is a (proper) vertex coloring ϕ : V → S v2V Lv such that ϕ(v) ∈ Lv for all v ∈ V and ϕ(u) 6= ϕ(v) for all uv ∈ E. If such a ϕ exists, G is said to be list colorable. The choice number of G is the smallest natural number k for which G is list colorable whenever each list contains at least k colors. In this note we initiate the study of graphs in which the choice number equals...
In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. If in a partially ordered set, all chains are finite and all antichains have size , then the set has size for any regular . Every partially ordered set without a maximal element has two disjoint cofinal sub sets – CS. Every partially ordered set...
In this paper we present some hypergraphs which are chromatically characterized by their chromatic polynomials. It occurs that these hypergraphs are chromatically unique. Moreover we give some equalities for the chromatic polynomials of hypergraphs generalizing known results for graphs and hypergraphs of Read and Dohmen.
We color the vertices of each of the edges of a C-hypergraph (or cohypergraph) in such a way that at least two vertices receive the same color and in every proper coloring of a B-hypergraph (or bihypergraph), we forbid the cases when the vertices of any of its edges are colored with the same color (monochromatic) or when they are all colored with distinct colors (rainbow). In this paper, we determined explicit formulae for the chromatic polynomials of C-hypercycles and B-hypercycles
Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and...