Circular colouring and orientation of graphs
type: Item
instance of: scholarly article
title: Circular colouring and orientation of graphs
zbMATH Open document ID: 1025.05028
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: The author proves that if a graph \(G\) has an orientation \(D\) such that for each cycle \(C\) with \(d|C|\pmod k\in \{1,2,\dots, 2d-1\}\) we have \(|C|/|C^+|\leq k/d\) and \(|C|/|C^-|\leq k/d\), then \(G\) has a \((k,d)\)-colouring and hence the circular chromatic number of \(G\) is at most \(k/d\). The concept of circular chromatic number is a natural generalization of the chromatic number from many different points of view.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 1843846
zbMATH Keywords: chromatic number
zbMATH Keywords: cycle
zbMATH Keywords: orientation
author: Xuding Zhu
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
full work available at URL: jctb.2002.2117
OpenAlex ID: W2051447029
cites work: On (k,d)-colorings and fractional nowhere-zero flows
cites work: A Theorem on n-Coloring the Points of a Linear Graph
cites work: Graph coloring in linear time
cites work: Circular chromatic number: A survey
DOI: 10.1006/JCTB.2002.2117
description: scientific article; zbMATH DE number 1843846