Total Colorings of Planar Graphs without Small Cycles

Let G be a planar graph with maximum degree Δ. It is proved that if Δ ≥ 8 and G is free of k-cycles for some k ∈ {5,6}, then the total chromatic number χ′′(G) of G is Δ + 1. This work is supported by a research grant NSFC(60673047) and SRFDP(20040422004) of China. Received: February 27, 2007. Final version received: December 12, 2007.     

Aspects of strong compactness, measurability, and indestructibility

 We prove three theorems concerning Laver indestructibility, strong compactness, and measurability. We then state some related open questions. Received: 11 December 1999 / Revised version: 17 September 2000 / Published online: 2 September 2002 Mathematics Subject classification (2000): 03E35, 03E55 Keywords or phrases: Measurable cardinal – Strongly compact cardinal – Supercompact cardinal – Indestructibility     

A Note on the Game Chromatic Index of Graphs

In this note we prove that the game chromatic index χ _g ^′(G) of a graph G of arboricity k is at most Δ + 3k − 1. This improves a bound obtained by Cai and Zhu [J. Graph Theory 36 (2001), 144–155] for k-degenerate graphs. Tomasz Bartnicki: Research of the first author is supported by a PhD grant from Polish Ministry of Science and Higher Education N201 2128 33. Received: November 1, 2006. Final version received: December 22, 2007.     

Super-Magic Complete k-Partite Hypergraphs

 We deal with complete k-partite hypergraphs and we show that for all k≥2 and n≠2,6 its hyperedges can be labeled by consecutive integers 1,2,…,n ^k such that the sum of labels of the hyperedges incident to (k−1) particular vertices is the same for all (k−1)-tuples of vertices from (k−1) independent sets. Received: December 8, 1997 Final version received: July 26, 1999     

Matrix algebras in Quasi-Newton methods for unconstrained minimization

Summary.  In this paper a new class of quasi-Newton methods, named ℒQN, is introduced in order to solve unconstrained minimization problems. The novel approach, which generalizes classical BFGS methods, is based on a Hessian updating formula involving an algebra ℒ of matrices simultaneously diagonalized by a fast unitary transform. The complexity per step of ℒQN methods is O(n log n), thereby improving considerably BFGS computational efficiency. Moreover, since ℒQN's iterative scheme utilizes single-indexed arrays, only O(n) memory allocations are required. Global convergence properties are investigated. In particular a global convergence result is obtained under suitable assumptions on f. Numerical experiences [7] confirm that ℒQN methods are particularly recommended for large scale problems. Received December 30, 2001 / Revised version received December 20, 2001 / Published online November 27, 2002 Mathematics Subject Classification (1991): 65K10 Correspondence to: P. Zellini     

Claws in Rotational Tournaments

 A claw is a rooted tree whose each branch is a directed path starting at the root. We prove that each rotational tournament on 2n+1 vertices contains all claws with 2n edges and at most n branches. Received: December 15, 1999 Final version received: April 18, 2001 Acknowledgements. The authors wish to express their gratitude to the referee for valuable remarks, suggestions and comments that led to an improved paper.     

Remarks on the uniqueness of comparable renormalized solutions of elliptic equations with measure data

We give a partial uniqueness result concerning comparable renormalized solutions of the nonlinear elliptic problem -div(a(x,Du))=μ in Ω, u=0 on ∂Ω, where μ is a Radon measure with bounded variation on Ω. Received: December 27, 2000 Published online: December 19, 2001     

Colouring Arcwise Connected Sets in the Plane II

Let ? be the family of finite collections ? where ? is a collection of bounded, arcwise connected sets in ℝ² where for any S,T∈? such that S∩T≠?, it holds that S∩T is arcwise connected. Given ? is triangle-free, and provided the chromatic number χ(G) of the intersection graph G=G(?) of ? is sufficiently large, there exists α>1 independent of ? such that there is a subcollection ?^′⊂? of at most 5 sets with the property that the sets of ? surrounded by ?^′ induce an intersection graph H where . Received: November 13, 1995 Final version received: December 3, 1998     

From Intersectors to Successors

 A geometric graph any two line segments of which intersect is called an intersector. This notion will be generalized in order to obtain new results which are not true for this (restricted) category. Received: December 8, 1997 Final version received: January 12, 2000     

Online algorithms: a survey

 During the last 15 years online algorithms have received considerable research interest. In this survey we give an introduction to the competitive analysis of online algorithms and present important results. We study interesting application areas and identify open problems. Received: December 1, 2002 / Accepted: April 28, 2003 Published online: May 28, 2003 Mathematics Subject Classification (1991): 68W25, 68W40     

Maximum Number of Contractible Edges on Hamiltonian Cycles of a 3-Connected Graph

 We show that if G is a 3-connected hamiltonian graph of order at least 5, then there exists a hamiltonian cycle C of G such that the number of contractible edges of G which are on C is greater than or equal to . Received: July 31, 2000 Final version received: December 12, 2000 Acknowledgments. I would like to thank Professor Yoshimi Egawa for the help he gave to me during the preparation of this paper.