The circular chromatic index
type: Item
instance of: scholarly article
title: The circular chromatic index
zbMATH Open document ID: 1055.05052
author: Andrea Hackmann
author: Arnfried Kemnitz
published in: Discrete Mathematics
publication date: 2004-10-01T00:00:00Z
review text: Given positive integers \(k,d,\;k \geq 2d\), a \((k,d)\)-edge coloring of a graph \(G\) is a mapping \(c:\;E(G) \to \{0,1,\dots, k-1\}\) such that \(d \leq | c(e_i) - c(e_j)| \leq k-d\) whenever two edges \(e_i,e_j\) are adjacent. The authors introduce the circular chromatic index \(\chi_c'(G)\) defined as \(\chi_c'(G) = \inf\{\frac{k}{d}:\;G\) has a \((k,d)\)-edge coloring\(\}\). They prove that, in the definition, the infimum can be replaced by the minimum; further, it is shown that if \(G\) is Class 1, then \(\chi_c'(G) = \Delta(G)\), and if \(G\) is Class 2, then either \(\chi_c'(G) = \Delta(G) + 1\) or \(\Delta(G) + \frac{1}{\alpha'(G)} \leq \chi_c'(G) \leq \Delta(G) + \frac{\alpha'(G) - 1}{\alpha'(G)}\) (where \(\alpha'(G)\) is the edge independence number of \(G\)). Also, there are computed the exact values of \(\chi_c'\) for cycles, complete graphs and the Petersen graph.
reviewed by: Tomáš Madaras
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2105615
zbMATH Keywords: star chromatic number
zbMATH Keywords: circular chromatic number
zbMATH Keywords: star chromatic index
zbMATH Keywords: circular chromatic index
zbMATH Keywords: edge coloring
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.050
OpenAlex ID: W2116902851
cites work: A note on the star chromatic number
cites work: Q4871044
cites work: Star chromatic number
cites work: Star chromatic numbers and products of graphs
cites work: Circular chromatic number: A survey
DOI: 10.1016/J.DISC.2003.11.050
description: scientific article; zbMATH DE number 2105615