Decompositions of graphs and hypergraphs into isomorphic factors with a given diameter
An edge coloring of a plane graph G is facially proper if no two faceadjacent edges of G receive the same color. A facial (facially proper) parity edge coloring of a plane graph G is an (facially proper) edge coloring with the property that, for each color c and each face f of G, either an odd number of edges incident with f is colored with c, or color c does not occur on the edges of f. In this paper we deal with the following question: For which integers k does there exist a facial (facially proper)...
W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.
We study new equivalence relations in spatial graph theory. We consider natural generalizations of delta link-homotopy on links, which is an equivalence relation generated by delta moves on the same component and ambient isotopies. They are stronger than edge-homotopy and vertex-homotopy on spatial graphs which are natural generalizations of link-homotopy on links. Relationship to existing familiar equivalence relations on spatial graphs are stated, and several invariants are defined by using the...
We show that the dimer model on a bipartite graph on a torus gives rise to a quantum integrable system of special type, which we call acluster integrable system. The phase space of the classical system contains, as an open dense subset, the moduli space of line bundles with connections on the graph . The sum of Hamiltonians is essentially the partition function of the dimer model. We say that two such graphs and areequivalentif the Newton polygons of the corresponding partition functions...