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

Abstract

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 S_k and E_k, where S_k contains all graphs of maximum degree at most k and E_k 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, maximum
degree.