Advanced Search

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph $G$, a hereditary graph property $𝒫$ and $l\ge 1$ we define ${\chi }_{𝒫,l}^{\text{'}}\left(G\right)$ to be the minimum number of colours needed to properly colour the edges of $G$, such that any subgraph of $G$ induced by edges coloured by (at most) $l$ colours is in $𝒫$. We present a necessary and sufficient condition for the existence of ${\chi }_{𝒫,l}^{\text{'}}\left(G\right)$. We focus on edge-colourings of graphs with respect to the hereditary properties...

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

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

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, $a_i$ 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...