An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be additive hereditary properties of graphs. The generalized chromatic number ${\chi }_{}\left(\right)$ is defined as follows: ${\chi }_{}\left(\right)=n$ iff ⊆ ⁿ but ${⊊}^{n-1}$. We investigate the generalized chromatic numbers of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ and ₖ.

Let P be a graph property and r,s ∈ N, r ≥ s. A strong circular (P,r,s)-colouring of a graph G is an assignment f:V(G) → {0,1,...,r-1}, such that the edges uv ∈ E(G) satisfying |f(u)-f(v)| < s or |f(u)-f(v)| > r - s, induce a subgraph of G with the propery P. In this paper we present some basic results on strong circular (P,r,s)-colourings. We introduce the strong circular P-chromatic number of a graph and we determine the strong circular P-chromatic number of complete graphs for additive...

Gallai and Roy proved that a graph is k-colorable if and only if it has an orientation without directed paths of length k. We initiate the study of analogous characterizations for the existence of generalized graph colorings, where each color class induces a subgraph satisfying a given (hereditary) property. It is shown that a graph is partitionable into at most k independent sets and one induced matching if and only if it admits an orientation containing no subdigraph from a family of k+3 directed...

We study the generalized $k$-connectivity ${\kappa }_k\left(G\right)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$-edge-connectivity ${\lambda }_k\left(G\right)$. We determine the exact value of ${\kappa }_k\left(G\right)$ and ${\lambda }_k\left(G\right)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k=3$.

We construct a subalgebra ${\Sigma }^{\prime }\left(W_n\right)$ of dimension $2·3^{n-1}$ of the group algebra of the Weyl group $W_n$ of type $B_n$ containing its usual Solomon algebra and the one of ${𝔖}_n$: ${\Sigma }^{\prime }\left(W_n\right)$ is nothing but the Mantaci-Reutenauer algebra but our point of view leads us to a construction of a surjective morphism of algebras ${\Sigma }^{\prime }\left(W_n\right)\to \mathbf{Z}\mathrm{Irr}\left(W_n\right)$. Jöllenbeck’s construction of irreducible characters of the symmetric group by using the coplactic equivalence classes can then be transposed to $W_n$. In an appendix, P. Baumann and C. Hohlweg present in an explicit and...

The purpose of this paper is to present some basic properties of 𝓟-dominating, 𝓟-independent, and 𝓟-irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let and be hereditary properties of graphs. The generalized edge-chromatic number ${\rho }_{}^{\text{'}}\left(\right)$ is defined as the least integer n such that ⊆ n. We investigate the generalized edge-chromatic numbers of the properties → H, ₖ, ₖ, *ₖ, ₖ and ₖ.

Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]s be the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]s such that for each i ∈ ℤr the following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are disjoint. If...

An additive and hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be two additive and hereditary graph properties and let r, s be integers such that r ≥ s Then an [...] fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph of property P, all...

Let P and Q be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s -fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph with property P, all edges of color i induce a subgraph with property Q and vertices and incident edges have been assigned disjoint sets of colors. The...

Hovey introduced A-cordial labelings in [4] as a simultaneous generalization of cordial and harmonious labelings. If A is an abelian group, then a labeling f: V(G) → A of the vertices of some graph G induces an edge-labeling on G; the edge uv receives the label f(u) + f(v). A graph G is A-cordial if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one. Research on A-cordiality...