×

Homomorphisms of Cayley graphs and cycle double covers. (English) Zbl 1443.05129

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. M. DeVos [“A homomorphism problem for flows”, 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.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C21 Flows in graphs
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Archdeacon. Face colorings of embedded graphs.J. Graph Theory, 8(3):387-398, 1984. · Zbl 0545.05036
[2] M. DeVos. A homomorphism problem for flows.Open Problem Garden. http://www.openproblemgarden.org/op/a_homomorphism_problem_for_flows, [retrieved 2020-02-28]. · Zbl 1371.11019
[3] R. Diestel.Graph theory, volume 173 ofGraduate Texts in Mathematics. Springer, Berlin, fifth edition, 2017. · Zbl 1375.05002
[4] L. A. Goddyn, M. Tarsi, and C.-Q. Zhang. On (k, d)-colorings and fractional nowherezero flows.J. Graph Theory, 28(3):155-161, 1998. · Zbl 0922.05027
[5] F. Jaeger. Nowhere-zero flow problems.Selected topics in graph theory, 3:71-95, 1988. · Zbl 0658.05034
[6] P. D. Seymour. Nowhere-zero 6-flows.J. Combin. Theory Ser. B, 30(2):130-135, 1981. · Zbl 0474.05028
[7] W. T. Tutte. On the imbedding of linear graphs in surfaces.Proc. London Math. Soc., s2-51(1):474-483, 1949. · Zbl 0033.30803
[8] W. T. Tutte. A contribution to the theory of chromatic polynomials.Canadian J. Math., 6:80-91, 1954. · Zbl 0055.17101
[9] C.-Q. Zhang.Integer flows and cycle covers of graphs, volume 205 ofMonographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, New York, 1997.
[10] C.-Q. Zhang.Circuit Double Cover of Graphs. London Mathematical Society Lecture Note Series. Cambridge University Press, 2012. · Zbl 1250.05006
[11] X.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.