Users without a subscription are not able to see the full content.

## Pavol Hell and Jaroslav Nesetril

Print publication date: 2004

Print ISBN-13: 9780198528173

Published to Oxford Scholarship Online: September 2007

DOI: 10.1093/acprof:oso/9780198528173.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2019. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see www.oxfordscholarship.com/page/privacy-policy).date: 22 July 2019

# COLOURING—VARIATIONS ON A THEME

Chapter:
(p.192) 6 COLOURING—VARIATIONS ON A THEME
Source:
Graphs and Homomorphisms
Publisher:
Oxford University Press
DOI:10.1093/acprof:oso/9780198528173.003.0006

This chapter sets out certain particular classes of homomorphism problems that have been investigated as variants of graph colourings. The homomorphism perspective unifies these concepts and offers new questions. The chapter includes a discussion of the circular chromatic number, the fractional chromatic number, the $T$-span, and the oriented chromatic number. Highlights include a number of equivalent definitions of the circular chromatic number in terms of $H$-colourability; in terms of a geometric representation, in terms of orientations implying, for instance, Minty’s result on chromatic numbers; and in terms of schedule concurrency. For fractional chromatic numbers, equivalent formulations are given in terms of Kneser graphs, integer linear programs, and zero-sum games, and they are related in several ways to the circular chromatic numbers. Homomorphisms amongst Kneser graphs are investigated, and a proof of Kneser’s conjecture is given. It is shown that the span for any set $T$ of the cliques $K_n$ has a limit, which is closely related to the fractional chromatic number of an associated graph. Bounds on the oriented chromatic numbers of planar and outerplanar graphs are given, and oriented chromatic numbers are related to acyclic chromatic numbers.

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.