×

The circular chromatic number of series-parallel graphs. (English) Zbl 0944.05037

It is proved that if the girth of a series-parallel graph \(G\) is at least \(2 \lfloor (3k-1)/2 \rfloor\), then the circular chromatic number \(\chi_c(G)\) of \(G\) is at most \(4k/(2k-1)\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite

References:

[1] Bondy, J Graph Theory 14 pp 479– (1990) · Zbl 0706.05022
[2] Er?s, Canad J Math 11 pp 34– (1959) · Zbl 0084.39602
[3] and The circular chromatic number of series-parallel graphs with large girth, manuscript, 1999.
[4] and Geometric algorithms and combinatorial Optimization, Second ed., Springer-Verlag, New York, pp. 274, 1993. · Zbl 0837.05001
[5] Moser, J Graph Theory 24 pp 33– (1997) · Zbl 0870.05017
[6] Ne?et?il, J Graph Theory 23 pp 151– (1996) · Zbl 0858.05045
[7] Matroid theory, Oxford Sci, Oxford, 1992.
[8] and The circular chromatic number of series-parallel graphs of large odd girth, manuscript, 1999.
[9] and Density of the circular chromatic numbers of series- parallel graphs, manuscript, 1999.
[10] Steffen, Combin 16 pp 439– (1996) · Zbl 0860.05036
[11] Vince, J Graph Theory 12 pp 551– (1988) · Zbl 0658.05028
[12] Zhu, J Graph Theory 16 pp 557– (1992) · Zbl 0766.05033
[13] Zhu, J Graph Theory 23 pp 33– (1996) · Zbl 0864.05037
[14] Zhu, J Combin Theory Ser B 76 pp 170– (1999) · Zbl 0933.05053
[15] Zhu, Taiwan J Math
[16] Zhu, Discrete Math
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.