Leptospermum petersonii as a Potential Natural Food Preservative

Leptospermum petersonii (family Myrtaceae) is often cultivated for ornamental purposes but also serves as a rich source of bioactive essential oils. While several studies focused on the activities of the essential oils, this study analysed the potential of spent L. petersonii leaves as a natural food preservative. Method: We investigated the in vitro antioxidant and antimicrobial activities of crude L. petersonii extracts against activities of the purified isolated flavonoid, 6-methyltectochrysin, which was characterized using spectroscopic methods. The antioxidant assays followed ORAC, FRAP and TEAC tests. The antimicrobial activities of the extract and purified flavonoid were analysed against six multi-drug resistant microbial strains in broth dilution assays. Result: The results revealed that both the crude extracts and isolated 6-methyltectochrysin exhibited positive radical ion scavenging antioxidant potential, however the crude extract was about 6-fold more potent antioxidant than the purified 6-methyltectochrysin. The crude extract also showed strong antimicrobial activities against Bacillus cereus, and even more potent antimicrobial agent than the reference ampicillin antibiotic against Klebsiella pneumoniae subsp. pneumoniae. A higher resistance was observed for the tested Gram-negative strains than for the Gram-positive ones. 6-methyltectochrysin was generally inactive in the antimicrobial assays. Conclusion: The crude methanolic extract showed significant bioactivity which validates the medicinal relevance of the plant. The observed biological activities, especially against a notorious strain of B. cereus, suggest that L. petersonii could be a promising natural source of food preservatives.     

A conjecture of Borodin and a coloring of Grünbaum

In 1976, Borodin conjectured that every planar graph has a 5‐coloring such that the union of every k color classes with 1 ≤ k ≤ 4 induces a (k—1)‐degenerate graph. We prove the existence of such a coloring using 18 colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:139–147, 2008     

Integral mixed unit interval graphs

We characterize graphs that have intersection representations using unit intervals with open or closed ends such that all ends of the intervals are integral in terms of infinitely many minimal forbidden induced subgraphs. Furthermore, we provide a linear-time algorithm that decides if a given interval graph admits such an intersection representation.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

Matchings in graphs of odd regularity and girth

We establish lower bounds on the matching number of graphs of given odd regularity d$d$ and odd girth g$g$, which are sharp for many values of d$d$ and g$g$. For d=g=5$d=g=5$, we characterize all extremal graphs.     

Ramsey Results for Cycle Spectra

Let denote the set of lengths of cycles of a graph G of order n and let denote the complement of G. We show that if , then contains all odd ? with and all even ? with , where and denote the maximum odd and the maximum even integer in , respectively. From this we deduce that the set contains at least integers, which is sharp.     

On αrγs(k)-perfect graphs

For some integer k0 and two graph parameters π and τ, a graph G is called πτ(k)-perfect, if π(H)−τ(H)k for every induced subgraph H of G. For r1 let α_r and γ_r denote the r-(distance)-independence and r-(distance)-domination number, respectively. In (J. Graph Theory 32 (1999) 303–310), I. Zverovich gave an ingenious complete characterization of α₁γ₁(k)-perfect graphs in terms of forbidden induced subgraphs. In this paper we study α_rγ_s(k)-perfect graphs for r,s1. We prove several properties of minimal α_rγ_s(k)-imperfect graphs. Generalizing Zverovich's main result in (J. Graph Theory 32 (1999) 303–310), we completely characterize α_2r−1γ_r(k)-perfect graphs for r1. Furthermore, we characterize claw-free α₂γ₂(k)-perfect graphs.     

Upper bounds on the uniquely restricted chromatic index

Golumbic, Hirst, and Lewenstein define a matching in a simple, finite, and undirected graph to be uniquely restricted if no other matching covers exactly the same set of vertices. We consider uniquely restricted edge-colorings of , defined as partitions of its edge set into uniquely restricted matchings, and study the uniquely restricted chromatic index of , defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph , where is the classical chromatic index, the acyclic chromatic index, and the strong chromatic index of . While Vizing's famous theorem states that is either the maximum degree of or , two famous open conjectures due to Alon, Sudakov, and Zaks, and to Erdős and Nešetřil concern upper bounds on and in terms of . Since is sandwiched between these two parameters, studying upper bounds in terms of is a natural problem. We show that with equality if and only if some component of is . If is connected, bipartite, and distinct from , and is at least , then, adapting Lovász's elegant proof of Brooks’ theorem, we show that . Our proofs are constructive and yield efficient algorithms to determine the corresponding edge-colorings.