1 - 2 of 2
Number of results to display per page
Search Results
2. Edge-colouring of graphs and hereditary graph properties
- Creator:
- Dorfling, Samantha and Vetrík, Tomáš
- Format:
- print, bez média, and svazek
- Type:
- model:article and TEXT
- Subject:
- mathematics, grafy, edge-colouring, proper colouring, hereditary graph property, 13, and 51
- Language:
- English
- Description:
- 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 P and l\geqslant 1 we define X{'_{P,l}} 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 P. We present a necessary and sufficient condition for the existence of X{'_{P,l}} . We focus on edge-colourings of graphs with respect to the hereditary properties Ok and Sk, where Ok contains all graphs whose components have order at most k+1, and Sk contains all graphs of maximum degree at most k. We determine the value of X{'_{{S_k},l}}(G) for any graph G,k \geqslant 1, l\geqslant 1 and we present a number of results on X{'_{{O_k},l}}(G) ., Samantha Dorfling, Tomáš Vetrík., and Obsahuje seznam literatury
- Rights:
- http://creativecommons.org/publicdomain/mark/1.0/ and policy:public