Colorings and orientations of matrices and graphs

MaRDI QIDQ2500980zbMATH OpenFDO

Authors Uwe Schauz

Publication date 30 August 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/126664, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r61.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Eulerian orientationshypergraph coloringslist coloringsmatrix choosabilitymatrix coloringspermanent

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15)

Review text

Summary: 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.

Recommendations

• scientific article; zbMATH DE number 599411
• Permanent index of matrices associated with graphs
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• Colorings and orientations of graphs
• On two generalizations of the Alon-Tarsi polynomial method

Cited in

(13)

• Similarity matrices for colored graphs
• Colorings and orientations of graphs
• Orthogonal colorings of graphs
• Orientations of 1-factors and the list edge coloring conjecture
• Matrix choosability
• Intercalate coloring of matrices and the Yuzvinsky conjecture
• scientific article; zbMATH DE number 5531990 (Why is no real title available?)
• Coloring an Orthogonality Graph
• Graph colorings and acyclic orientations
• Multicolor reordering of sparse matrices resulting from irregular grids
• scientific article; zbMATH DE number 599411 (Why is no real title available?)
• scientific article; zbMATH DE number 3221981 (Why is no real title available?)
• Punctured combinatorial Nullstellensätze

This page was built for publication: Colorings and orientations of matrices and graphs

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