Non-proper edge-colouring of graphs and hereditary graph properties

A graph property is any isomorphism-closed class of graphs. A property P is hereditary if, whenever a graph G is in P, and H is a subgraph of G, then H is also in P. For a hereditary graph property P, positive integer l and a graph G, let ′ ρP,l(G) be the minimum number of colours needed to colour the edges of G, such that any subgraph of G induced by edges coloured with (at most) l colours is in P. We study the properties Sk and Ek, where Sk contains all graphs of maximum degree at most k and Ek contains graphs, whose components have at most k edges. We present results on ρ′Sk,l(G) and ρ'εk,l(G) for various graphs G. We prove that for graphs G of maximum degree Δ we have ⌈ Δ-k/ ⌊k/l ⌋⌉ +l ≤ ρ′Sk,l(G) ≤⌈ Δ+1/ ⌊k/l ⌋ ⌉ and we use Erdos-Lovasz local lemma to show that for l≤ k, ρ'εk,l(G)≤ ⌈[ 3(k+1)(2klΔ)k/ (l-1)/!k! ]1/k+1-l⌉.Mathematics Subject Classication (2010): 05C15, 05C35.Key words: Edge-colouring, non-proper colouring, hereditary graph property, maximumdegree