Homomorphisms of Cayley graphs and cycle double covers
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
An \(M\)-flow \(f: E \to M\), where \(M\) is an abelian group is called an \((M, B)\)-flow if \(f(e)\in B\ \forall e\in E\). Here \(B\) is a symmetric subset of \(M\) with non-zero elements. \(f\) is also called a nowhere zero \(M\)-flow. An inspiration for concentrating on such flows is the fact that a planar graph has a proper face \(k\)-coloring if and only if it has a nowhere-zero \(Z_k\)-flow. \textit{M. DeVos} [``A homomorphism problem for flows, \url{http://www.openproblemgarden.org/op/a_homomorphism_problem_for_flows}] has raised the following conjecture: ``If \(M\), \(M_0\) are abelian groups and \(B\subseteq M\), \(B_0\subseteq M_0\) their symmetric subsets. If there is a graph homomorphism from the Cayley-graph Cay\((M, B)\) into Cayley-graph Cay\((M_0, B_0)\), then every graph with an \((M, B)\)-flow has an \((M_0,B_0)\)-flow. It is still open. In this paper, the authors develop a new framework under which the equivalence of this conjecture with the conjecture that ``all graphs have homomorphism property is proven. Furthermore, they give a new formulation of the homomorphism property called strong homomorphism property and along with a technical definition namely cubification of a digraph \(G\) have established that every non-cubic graph can be reduced to a smaller cubic one. To conclude they show that flows obtained from the homomorphism property or the strong homomorphism property can be transformed into an oriented cycle double cover and deduce that every bridgeless graph has an orientable cycle double cover with at most 6 cycles. The proof technique involved is very new and interesting and opens up new ideas for further exploration.
- A Contribution to the Theory of Chromatic Polynomials
- A short proof of Kneser's addition theorem for abelian groups
- Circuit double cover of graphs
- Face colorings of embedded graphs
- Graph theory
- scientific article; zbMATH DE number 4075098 (Why is no real title available?)
- Nowhere-zero 6-flows
- On (k,d)-colorings and fractional nowhere-zero flows
- On the Imbedding of Linear Graphs in Surfaces
- On covers of graphs by Cayley graphs
- Flow-continuous mappings -- the influence of the group
- Homomorphisms of binary Cayley graphs
- scientific article; zbMATH DE number 5566771 (Why is no real title available?)
- Induced cayley graphs and d0ouble covers
- Homomorphisms of Cayley graphs and cycle double covers
- Orthogonal double covers of Cayley graphs
This page was built for publication: Homomorphisms of Cayley graphs and cycle double covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918869)
