The circular chromatic index of graphs of high girth

DOI10.1016/J.JCTB.2006.03.002MaRDI QIDQ858677zbMATH OpenOpenAlexWikidataFDO

Authors Tomáš Kaiser, Daniel Král', Riste Škrekovski, Xuding Zhu

Publication date 11 January 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2006.03.002

zbMATH Keywords

circular chromatic numbercircular edge-coloringfractional chromatic indexgirth conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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\,. \)

Recommendations

• The circular chromatic index
• Circular chromatic index of graphs of maximum degree 3
• Circular edge-colorings of cubic graphs with girth six
• Circular chromatic indices of even degree regular graphs
• Circular chromatic number: A survey

Cites work

• A condition for matchability in hypergraphs
• A note on the star chromatic number
• A revival of the girth conjecture
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Circular chromatic number: A survey
• Combinatorics 79. Part I
• Domination numbers and homology
• Hall's theorem for hypergraphs
• High-girth graphs avoiding a minor are nearly bipartite
• scientific article; zbMATH DE number 3754754 (Why is no real title available?)
• scientific article; zbMATH DE number 867669 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Independent systems of representatives in weighted graphs
• Maximum matching and a polyhedron with 0,1-vertices
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Snarks without small cycles
• Star chromatic number
• Star chromatic numbers of graphs
• The clique complex and hypergraph matching
• The Factorization of Linear Graphs
• Transversals of Vertex Partitions in Graphs
• Triangulated spheres and colored cliques

Cited in

(16)

• Neighbor-distinguishing \(k\)-tuple edge-colorings of graphs
• Graphs of large girth with prescribed partial circular colourings
• A revival of the girth conjecture
• The circular chromatic index
• Circular chromatic indices of even degree regular graphs
• A note on circular chromatic number of graphs with large girth and similar problems
• Circular chromatic index of Cartesian products of graphs
• Finding independent transversals efficiently
• Ring graphs and Goldberg's bound on chromatic index
• Circular chromatic index of graphs of maximum degree 3
• Circular chromatic indices of regular graphs
• Circular edge-colorings of cubic graphs with girth six
• Circular edge-colorings of cubic graphs with girth six
• Constructing graphs with no independent transversals
• The circular chromatic index of some Class 2 graphs
• Circular total chromatic numbers of graphs

This page was built for publication: The circular chromatic index of graphs of high girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q858677)