Colorings and orientations of graphs. (English) Zbl 0756.05049

Summary: Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: If \(G\) is a directed graph with maximum outdegree \(d\), and if the number of Eulerian subgraphs of \(G\) with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a set \(S(v)\) of \(d+1\) colors for each vertex \(v\) of \(G\) there is a legal vertex-coloring of \(G\) assigning to each vertex \(v\) a color from \(S(v)\).


05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI


[1] N. Alon, S. Friedland, andG. Kalai: Regular subgraphs of almost regular graphs,J. Combinatorial Theory, Ser. B37 (1984), 79-91. · Zbl 0527.05059
[2] N. Alon, C. McDiarmid, andB. Reed: Star Arboricity, to appear.
[3] N. Alon, andM. Tarsi: A nowhere zero point in linear mappings,Combinatorica 9 (1989), 393-395. · Zbl 0717.05021
[4] J. A. Bondy, R. Boppana, andA. Siegel: Private communication.
[5] C. Berge:Graphs and Hypergraphs, Dunod, Paris, 1970. · Zbl 0334.05117
[6] B. Bollob?s:Extremal Graph Theory, Academic Press, New York, 1978.
[7] A. Chetwynd, andR. H?ggkvist: A note on list colorings,J. Graph Theory 13 (1989), 87-95. · Zbl 0674.05026
[8] P. Erd?s: Some old and new problems in various branches of combinatorics,Congressus Numerantium 23 (1979), 19-37.
[9] P. Erd?s, A. Rubin, andH. Taylor: Choosability in graphs,Congressus Numerantium 26 (1979), 125-157.
[10] I. Gessel: Tournaments and Vandermonde’s determinant,J. Graph Theory 3 (1979), 305-307. · Zbl 0433.05008
[11] R. L. Graham, S.-Y. R. Li, andW.-C. W. Li: On the structure oft-designs,SIAM J. Alg. Disc. Meth. 1 (1980), 8-14. · Zbl 0499.05012
[12] S.-Y. R. Li, andW.-C. W. Li: Independence numbers of graphs and generators of ideals,Combinatorical 1 (1981), 55-61. · Zbl 0524.05037
[13] R. P. Stanley: Acyclic orientations of graphs,Discrete Math. 5 (1973), 171-178. · Zbl 0258.05113
[14] M. Tarsi: On the decomposition of a graph into stars,Discrete Math. 36 (1981), 299-304. · Zbl 0467.05054
[15] V. G. Vizing: Coloring the vertices of a graph in prescribed colors (in Russian),Diskret. Analiz. 29,Metody Discret. Anal. v. Teorii Kodov i Shem 101 (1976), 3-10.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.