The Open UniversitySkip to content
 

Overlap colourings and homomorphisms of graphs

Holroyd, Fred and Watts, Ivor (2010). Overlap colourings and homomorphisms of graphs. The Quarterly Journal of Mathematics [in press].

Full text available as:
Full text not publicly available
Due to copyright restrictions, this file is not available for public download
Click here to request a copy from the OU Author.
DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1093/qmath/haq022
Google Scholar: Look up in Google Scholar

Abstract

An (r, λ) overlap colouring of a graph G has r colours at each vertex, any two adjacent vertices sharing exactly λ colours. A theory analogous to multichromatic and fractional chromatic theory is developed. In particular, all the overlap chromatic numbers of cycle graphs are computed. It is shown that if a graph G contains an odd cycle C2p+1 and has the same p-fold chromatic number as C2p+1, then all its overlap chromatic numbers are the same as those of C2p+1. The core of a graph is the smallest induced subgraph to which it has a homomorphism. It is shown that some pairs of graphs with the same multichromatic numbers have different sets of overlap chromatic numbers, and that some graphs with non-isomorphic cores have the same sets of overlap chromatic numbers. (In particular, any non-bipartite series-parallel graph has the same overlap chromatic as its smallest odd cycle.) Thus classifying graphs by overlap chromatic properties is intermediate between classifying them by multichromatic properties and classifying them by cores.

Item Type: Journal Article
Copyright Holders: 2010 Oxford University Press
ISSN: 0033-5606
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 24726
Depositing User: Fred Holroyd
Date Deposited: 23 Nov 2010 12:00
Last Modified: 12 Dec 2012 08:13
URI: http://oro.open.ac.uk/id/eprint/24726
Share this page:

Altmetrics

Scopus Citations

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk