The graph polynomial and the number of proper vertex coloring

Michael Tarsi

Annales de l'institut Fourier (1999)

  • Volume: 49, Issue: 3, page 1089-1093
  • ISSN: 0373-0956

Abstract

top
Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper k -colorings of a graph, which can be computed from its graph polynomial. The subject of this paper is another combinatorial interpretation of the same quantity, expressed in terms of the numbers of certain modulo k flows in the graph. Some relations between graph parameters can be obtained by combining these two formulas. For example: The number of proper 3-colorings of a 4-regular graph and the number of Eulerian orientations of that graph, have the same parity.

How to cite

top

Tarsi, Michael. "The graph polynomial and the number of proper vertex coloring." Annales de l'institut Fourier 49.3 (1999): 1089-1093. <http://eudml.org/doc/75357>.

@article{Tarsi1999,
abstract = {Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper $k$-colorings of a graph, which can be computed from its graph polynomial. The subject of this paper is another combinatorial interpretation of the same quantity, expressed in terms of the numbers of certain modulo $k$ flows in the graph. Some relations between graph parameters can be obtained by combining these two formulas. For example: The number of proper 3-colorings of a 4-regular graph and the number of Eulerian orientations of that graph, have the same parity.},
author = {Tarsi, Michael},
journal = {Annales de l'institut Fourier},
keywords = {proper vertex colorings; graph polynomial; edge-orientations; Eulerian orientations},
language = {eng},
number = {3},
pages = {1089-1093},
publisher = {Association des Annales de l'Institut Fourier},
title = {The graph polynomial and the number of proper vertex coloring},
url = {http://eudml.org/doc/75357},
volume = {49},
year = {1999},
}

TY - JOUR
AU - Tarsi, Michael
TI - The graph polynomial and the number of proper vertex coloring
JO - Annales de l'institut Fourier
PY - 1999
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 1089
EP - 1093
AB - Alon and Tarsi presented in a previous paper a certain weighted sum over the set of all proper $k$-colorings of a graph, which can be computed from its graph polynomial. The subject of this paper is another combinatorial interpretation of the same quantity, expressed in terms of the numbers of certain modulo $k$ flows in the graph. Some relations between graph parameters can be obtained by combining these two formulas. For example: The number of proper 3-colorings of a 4-regular graph and the number of Eulerian orientations of that graph, have the same parity.
LA - eng
KW - proper vertex colorings; graph polynomial; edge-orientations; Eulerian orientations
UR - http://eudml.org/doc/75357
ER -

References

top
  1. [1] N. ALON and M. TARSI, Colorings and orientations of graphs, Combinatorica, 12 (1992), 125-134. Zbl0756.05049MR93h:05067
  2. [2] N. ALON and M. TARSI, A note on graph colorings and graph polynomials, J. Comb. Theory, B 70 (1997), 197-201. Zbl0883.05050MR98c:05055
  3. [3] H. FLEISCHNER and M. STIEBITZ, A solution to a Colouring problem of P. Erdös, Discrete Math., 101 (1992), 39-48. Zbl0759.05037MR93g:05050
  4. [4] H. SACHS, Elementary proof of the cycle-plus-triangles theorem, in: Combinatorics, Paul Erdös is Eighty, Janos Bolyai Math. Soc., Budapest, 1993, Vol 1, 347-359. Zbl0797.05047MR94j:05082

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.