Let τ(G) denote the number of vertices in a longest path of the graph G and let k₁ and k₂ be positive integers such that τ(G) = k₁ + k₂. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V₁ and V₂ such that τ(G[V₁] ) ≤ k₁ and τ(G[V₂] ) ≤ k₂. We show that several classes of graphs have this partition property.
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 is defined as the least integer n such that ⊆ n. We investigate the generalized edge-chromatic numbers of the properties → H, ₖ, ₖ, *ₖ, ₖ and ₖ.
For a graph G and a vertex-coloring c:V(G) → 1,2, ...,k, the color code of a vertex v is the (k+1)-tuple (a₀,a₁, ...,aₖ), where a₀ = c(v), and for 1 ≤ i ≤ k, is the number of neighbors of v colored i. A recognizable coloring is a coloring such that distinct vertices have distinct color codes. The recognition number of a graph is the minimum k for which G has a recognizable k-coloring. In this paper we prove three conjectures of Chartrand et al. in [8] regarding the recognition number of cycles...
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that , the subgraph of G induced by , is in , for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property G ∈ : G has a (₁,...,ₙ)-decomposition. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such that = ₁⊕ ₂....
Page 1