A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

Cycle and circle tests of balance in gain graphs: Forbidden minors and their groups

We examine two criteria for balance of a gain graph, one based on binary cycles and one on circles. The graphs for which each criterion is valid depend on the set of allowed gain groups. The binary cycle test is invalid, except for forests, if any possible gain group has an element of odd order. Assuming all groups are allowed, or all abelian groups, or merely the cyclic group of order 3, we characterize, both constructively and by forbidden minors, the graphs for which the circle test is valid. It turns out that these three classes of groups have the same set of forbidden minors. The exact reason for the importance of the ternary cyclic group is not clear. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Achievable sets, brambles, and sparse treewidth obstructions

One consequence of the graph minor theorem is that for every k there exists a finite obstruction set Obs(TW?k). However, relatively little is known about these sets, and very few general obstructions are known. The ones that are known are the cliques, and graphs which are formed by removing a few edges from a clique. This paper gives several general constructions of minimal forbidden minors which are sparse in the sense that the ratio of the treewidth to the number of vertices n does not approach 1 as n approaches infinity. We accomplish this by a novel combination of using brambles to provide lower bounds and achievable sets to demonstrate upper bounds. Additionally, we determine the exact treewidth of other basic graph constructions which are not minimal forbidden minors.     

The influence of minor components on the structural reorganization in glassforming materials

Correlation of structure parameters of glasses and related crystals formed in homogeneous or heterogeneous nucleation processes by thermal treatment is discussed on the basis of DTA, TG and EGA measurements in relation to the textural patterns of the materials. For cordierite glass, crystallization of metastable disordered cordierite polymorphs is related to an exothermic heat evolution and simultaneous with a small weight loss (appr. 0.025%). By MS-EGA, evolution of water was determined during the transformation of the metastable melt to a metastable intermediate crystalline phase. Interpretation of the crystallization by comparing the available structure parameters of cordierite glasses and crystals alone is insufficient to explain the role of water in the kinetics of crystallization. Optical and electron microscopy of the primary crystallization phenomena show the metastable solid solution with low quartz-type structure. Interpretation of the crystallization behaviour in terms of conventional theory of nucleation and crystal growth is impossible.     

Anomalies of the partition coefficient and properties of crystals in the region of low concentrations of an isomorphous admixture. 1. Unusual decomposition of solid solutions of the NaCl—CdCl2 system

Solid solutions NaCl—CdCl₂ were studied in an interval of CdCl₂ concentrations of 0.05—3 mol.% by Raman spectroscopy. The molecular form Na₂CdCl₄ decomposes: Na₂CdCl₄ 2Na⁺ + Cd²⁺ + 2Cl₂ ^– + 2e^–; 2Na + 2e^– 2Na⁰. Free sodium atoms form color centers of crystal (F centers) in the region of jumpwise changing the partition coefficient of CdCl₂ in NaCl (K jump).     

A minimization version of a directed subgraph homeomorphism problem

We consider a special case of the directed subgraph homeomorphism or topological minor problem, where the host graph has a specific regular structure. Given an acyclic directed pattern graph, we are looking for a host graph of minimal height which still allows for an embedding. This problem has applications in compiler design for certain coarse-grain reconfigurable architectures. In this application domain, the task is to simultaneously schedule, bind and route a so-called data-flow graph, where vertices represent operations and arcs stand for data dependencies between the operations, given an orthogonal grid structure of reconfigurable processing elements (PEs) that have restricted communication abilities. We show that the problem of simultaneously scheduling, binding and routing is NP-complete by describing a logic engine reduction from NAE-3-SAT. This result holds even when the input graph is a directed tree with maximum indegree two. We also give a |V|^3/2-approximation algorithm. J. A. Brenner’s research supported by the DFG Research Center Matheon “Mathematics for key technologies”. J. C. van der Veen’s research supported by DFG Focus Program 1148, “Reconfigurable Architectures”, Grants FE 407/8-1 and FE 407/8-2.     

Design criteria for tetradentate phenanthroline-derived heterocyclic ligands to separate Am(Ⅲ) from Eu(Ⅲ)

To design novel phenanthroline-derived soft ligands for selectively separating minor actinides from lanthanides, four tetradentate phenanthroline-derived heterocyclic ligands(BTPhen, BPyPhen, BPzPhen, and BBizPhen) were constructed and their complexation behaviors with Am(ⅡI) and Eu(ⅡI) were systematically investigated by density functional theory(DFT) coupled with relativistic small-core pseudopotential. In all the 1:1-type species, the metal ion is in the center of the cavity and coordinates with two nitrogen atoms(N1 and N1′) of the phenanthroline skeleton and the other two nitrogen atoms(N2 and N2′) of the auxiliary groups. The bond lengths of Am–N are comparable to or even shorter than those of Eu–N bonds because the ionic radii of Am(ⅡI) are larger than those of Eu(ⅡI). Additionally, the negative ΔΔGAm/Eu value for the reaction of [M(H2O)4-(NO3)3] + L → ML(NO3)3 + 4H2 O indicates that the complexation reaction of Am(ⅡI) is more energetically favorable than that of Eu(ⅡI); this can be considered as an important design criterion to screen phenanthroline-derived ligands for MA(ⅡI) extraction. According to this criterion, the selectivity of tetradentate phenanthroline-derived ligands for separating Am(ⅡI) over Eu(ⅡI) follows the order of BTPhen BBizPhen BPyPhen BPzPhen.     

A variant of the isoperimetric problem,PartⅠ

This paper deals with the following isoperimetric problem in the plane:Among all regions with prescribed perimeter and covering a given line segment,what is the region that has the greatest area?     

An excluded minor theorem for the Octahedron plus an edge

Let G be the unique 4‐connected simple graph obtained by adding an edge to the Octahedron. Every 4‐connected graph that does not contain a minor isomorphic to G is either planar or the square of an odd cycle. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 124–130, 2008