Jump to ContentJump to Main Navigation
Graphs and Homomorphisms$
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 (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 31 October 2020



Graphs and Homomorphisms

Pavol Hell

Jaroslav Nešetřil

Oxford University Press

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.

Keywords:   circular colouring, fractional colouring, Kneser graph, Kneser Conjecture, oriented colouring, acyclic colouring, $T$-colouring, channel assignment problem, concurrency, zero-sum games

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.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .