The circular chromatic index of graphs of high girth
type: Item
instance of: scholarly article
title: The circular chromatic index of graphs of high girth
zbMATH Open document ID: 1114.05036
author: Tomáš Kaiser
author: Daniel Král'
author: Riste Škrekovski
author: Xuding Zhu
published in: Journal of Combinatorial Theory. Series B
publication date: 2007-01-11T00:00:00Z
review text: A proper circular \(l\)-coloring of a graph \(G\), for real \(l\geq1\), is a coloring of the vertices of \(G\) by real numbers from the interval \([0,l)\), such that the difference modulo \(l\) of the colors \(\gamma_1\) and \(\gamma_2\) assigned to two adjacent vertices is at least one, i.e. \(1\leq| \gamma_1-\gamma_2| \leq l-1\). The smallest real \(l\) for which there is a proper circular \(l\)-coloring is called the circular chromatic number of \(G\). The circular chromatic index \(\chi^{'}_c(G)\) of \(G\) is defined to be the circular chromatic number of \(L(G)\), the line graph of the graph \(G\). The main result of the paper is the following one: For any integer \(\Delta\geq1\) and real \(\varepsilon>0\), there exists a positive integer \(g\) such that if \(G\) is a graph of maximum degree \(\Delta\) and girth at least \(g\), then \( \chi^{'}_c(G)\leq\Delta+\varepsilon\,. \)
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5115316
zbMATH Keywords: circular edge-coloring
zbMATH Keywords: girth conjecture
zbMATH Keywords: fractional chromatic index
zbMATH Keywords: circular chromatic number
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
full work available at URL: j.jctb.2006.03.002
OpenAlex ID: W2047918966
Wikidata QID: Q57601523
cites work: Independent systems of representatives in weighted graphs
cites work: Triangulated spheres and colored cliques
cites work: Hall's theorem for hypergraphs
cites work: A note on the star chromatic number
cites work: Q3937450
cites work: Q4947393
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Transversals of Vertex Partitions in Graphs
cites work: High-girth graphs avoiding a minor are nearly bipartite
cites work: A condition for matchability in hypergraphs
cites work: Combinatorics 79. Part I
cites work: A revival of the girth conjecture
cites work: Snarks without small cycles
cites work: The clique complex and hypergraph matching
cites work: Domination numbers and homology
cites work: Aspects of structural combinatorics. (Graph homomorphisms and their use)
cites work: On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
cites work: Star chromatic numbers of graphs
cites work: The Factorization of Linear Graphs
cites work: Star chromatic number
cites work: Q4873782
cites work: Circular chromatic number: A survey
DOI: 10.1016/J.JCTB.2006.03.002
description: scientific article; zbMATH DE number 5115316