Article

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

Published in: Quaestiones Mathematicae
Volume 40 , issue 4 , 2017 , pages: 539–551

DOI: 10.2989/16073606.2017.1302516

Author(s): Samantha Dorfling Department of Mathematics and Applied Mathematics, South Africa , Elizabeth C.M. Maritz Department of Mathematics and Applied Mathematics, South Africa , Jon Smit Department of Mathematics and Applied Mathematics, South Africa , Tomáš Vetrík Department of Mathematics and Applied Mathematics, South Africa

Keywords: 05C15 , 05C35 , 05C15 , 05C35

Download full text Get new issue alerts

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 .

« On additive groups of associative and commutative rings

A note on lower bounds for the total domination number of digraphs »