On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Monodentate sigma-N and Bidentate sigma-N,sigma-N' Coordination of 1,1-Bis((N-p-tolylimino)diphenylphosphoranyl)ethane, CHCH(3)(PPh(2)=NC(6)H(4)-4-CH(3))(2), to Platinum(II)

The new ligand, 1,1-bis((N-p-tolylimino)diphenylphosphoranyl)ethane (1,1-BIPE), 1, has been synthesized by means of a Staudinger reaction of 1,1-bis(diphenylphosphino)ethane (1,1-dppe) with 2 equiv of p-tolylazide. Bridge-splitting reactions of Pt(2)Cl(4)(PR(3))(2) with 1 readily afforded sigma-N monodentate complexes, [PtCl(2)(PR(3)){1,1-BIPE-sigmaN}] (2a, PR(3) = PEt(3); 2b, PR(3) = PMe(2)Ph). Conversion of 2 into the six-membered platinacycle [PtCl(PR(3)){1,1-BIPE-sigmaN,sigmaN'}](+)[X](-) (3) (X = Cl, PtCl(3)(PR(3)), BF(4)) took place after prolonged stirring, its reaction rate being strongly dependent on the type of phosphine (>5 days for 2ain the presence of NaBF(4), 1 h for 2b) and the metal-to-ligand ratio. The compounds 1, 2, and 3 have been fully characterized by (1)H, (31)P{(1)H}, and (13)C{(1)H} NMR and IR spectroscopy, elemental analysis, or FAB mass spectroscopy. The molecular structures of CHCH(3)(PPh(2)=NC(6)H(4)-4-CH(3))(2) (1) and [PtCl(PMe(2)Ph){(N(pTol)=PPh(2))(2)CHCH(3)}](+)[Cl](-) (3b) have been determined by X-ray crystallography. Crystal data for 1: space group P2(1)/c with a = 8.9591(5) ?, b = 19.1961(12) ?, c = 21.9740(9) ?, beta = 105.069(4) degrees, V = 3649.1(3) ?(3), and Z = 4. The structure refinement converged to R = 0.080 and R(w) = 0.109. Crystal data for 3b: monoclinic, space group P2(1)/c with a = 12.4021(7) ?, b = 16.9705(11) ?, c = 23.760(2) ?, beta = 109.544(5) degrees, V = 4712.7(5) ?(3), and Z = 4. The structure refinement converged to R1 = 0.057, wR2 = 0.122. Variable temperature NMR spectroscopy has revealed that complexes 3 exclusively adopt a twisted boat conformation with the methyl group in equatorial position at low temperature, in agreement with the solid state structure of 3b as determined by X-ray crystallography. Boat-to-boat inversion is assumed to take place at temperatures above 293 K. Furthermore, for 3, hindered rotation of one of the p-tolyl substituents on nitrogen has been established at low temperatures.     

On the solitaire cone and its relationship to multi-commodity flows

The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to the 1960s, when the solitaire cone was first described by Boardman and Conway. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper we study the extremal structure of solitaire cones for a variety of boards, and relate their structure to the well studied metric cone. In particular we give:?1. an equivalence between the multicommodity flow problem with associated dual metric cone and a generalized peg game with associated solitaire cone;?2. a related NP-completeness result;?3. a method of generating large classes of facets;?4. a complete characterization of 0-1 facets;?5. exponential upper and lower bounds (in the dimension) on the number of facets;?6. results on the number of facets, incidence and adjacency relationships and diameter for small rectangular, toric and triangular boards;?7. a complete characterization of the adjacency of extreme rays, diameter, number of 2-faces and edge connectivity for rectangular toric boards. Received: July 1996 / Accepted: February 2000?Published online February 22, 2001     

On the $${\mathcal {}}$$-free extension complexity of the TSP

It is known that the extension complexity of the TSP polytope for the complete graph \(K_n\) is exponential in n even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets \({\mathcal {H}}\) of facet-defining inequalities of the TSP polytope. In particular, we consider the case when \({\mathcal {H}}\) is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called (h, t)-uniform inequalities, which may be of independent interest.     

A linear algorithm for computing the visibility polygon from a point

The hidden-line problem in two dimensions is a recurrent problem in computer graphics. In this paper a linear, and thus optimal, algorithm is exhibited for solving this problem.     

On the complexity of finding the convex hull of a set of points

An n log n lower bound is found for linear decision tree algorithms with integer inputs that either identify the convex hull of a set of points or compute its cardinality.     

Isotopically discriminated NMR spectroscopy: a tool for investigating complex protein interactions in vitro

A new NMR approach is presented for observing in vitro multicomponent protein-protein-ligand(s) interactions, which should help to understand how cellular networks of protein interactions operate on a molecular level and how they can be controlled with drugs. The method uniquely allows at least two polypeptide components of the mixture to be simultaneously closely monitored in a single sample, without increased signal overlap, and can be used to study complex (e.g., sequential, competitive, cooperative, allosteric, induced, etc.) binding events, witnessed by two polypeptides independently. One polypeptide is uniformly labeled with 15N and another with 15N and 13C. The 1H-15N correlation spectra are recorded for each of these molecules separately, discriminated on the basis of the type of 13C'/12C' atom attached to the amide group nitrogen. Any changes to the state of the two differently isotopically labeled molecules will be reported individually by fingerprint signals from amide groups, e.g., as unlabeled ligands are added. To our knowledge, no other technique currently exists which can monitor complex binding events in similar detail. The proposed method can be combined easily with traditional protein NMR techniques and incorporated in a variety of applications.     

A list heuristic for vertex cover

We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than .