Advanced Search

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 G = (V, E) be a simple graph of order n and i be an integer with i ≥ 1. The set X i ⊆ V(G) is called an i-packing if each two distinct vertices in X i are more than i apart. A packing colouring of G is a partition X = {X 1, X 2, …, X k} of V(G) such that each colour class X i is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by χρ(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t ≥ 3, then 9...

For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that [...] nΔ,D=ΔD2+O (ΔD2−1) $n_{\Delta ,D}={\Delta }^{\frac{D}{2}}+O\left({\Delta }^{\frac{D}{2}-1}\right)$ is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) $n_{\Delta ,D}=3{\Delta }^{\frac{D-1}{2}}+O\left({\Delta }^{\frac{D-1}{2}-1}\right)$ if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.