Article
Non-proper edge-colouring of graphs and hereditary graph properties
DOI:
10.2989/16073606.2017.1302516
Author(s):
Samantha DorflingDepartment of Mathematics and Applied Mathematics, South Africa, Elizabeth C.M. MaritzDepartment of Mathematics and Applied Mathematics, South Africa, Jon SmitDepartment of Mathematics and Applied Mathematics, South Africa, Tomáš VetríkDepartment of Mathematics and Applied Mathematics, South Africa,
Abstract
A graph property is any isomorphism-closed class of graphs. A property is hereditary if, whenever a graph G is in , and H is a subgraph of G, then H is also in . For a hereditary graph property , positive integer l and a graph G, let 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 . We study the properties and εk, where contains all graphs of maximum degree at most k and εk contains graphs, whose components have at most k edges. We present results on for various graphs G. We prove that for graphs G of maximum degree Δ we have and we use Erdős-Lovász local lemma to show that for .
Get new issue alerts for Quaestiones Mathematicae
