Colorings and orientations of matrices and graphs
The electronic journal of combinatorics, Tome 13 (2006)
We introduce colorings and orientations of matrices as generalizations of the graph theoretic terms. The permanent per$(A[\zeta|\xi])$ of certain copies $A[\zeta|\xi]$ of a matrix $A$ can be expressed as a weighted sum over the orientations or the colorings of $A$. When applied to incidence matrices of graphs these equations include Alon and Tarsi's theorem about Eulerian orientations and the existence of list colorings. In the case of planar graphs we deduce Ellingham and Goddyn's partial solution of the list coloring conjecture and Scheim's equivalency between not vanishing permanents and the four color theorem. The general concept of matrix colorings in the background is also connected to hypergraph colorings and matrix choosability.
DOI :
10.37236/1087
Classification :
05C15, 05C50, 15A15, 05C20, 05C45, 05C10
Mots-clés : permanent, Eulerian orientations, list colorings, matrix colorings, hypergraph colorings, matrix choosability
Mots-clés : permanent, Eulerian orientations, list colorings, matrix colorings, hypergraph colorings, matrix choosability
@article{10_37236_1087,
author = {Uwe Schauz},
title = {Colorings and orientations of matrices and graphs},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1087},
zbl = {1100.05039},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1087/}
}
Uwe Schauz. Colorings and orientations of matrices and graphs. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1087
Cité par Sources :