Home About us Contact
|
Home About us Contact | ||
|
|
||
New Upper Bound (new + upper_bound)
Selected AbstractsA new upper bound on the cyclic chromatic number,JOURNAL OF GRAPH THEORY, Issue 1 2007O. V. Borodin Abstract A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number ,c. Let ,* be the maximum face degree of a graph. There exist plane graphs with ,c = ,3/2 ,*,. Ore and Plummer [5] proved that ,c , 2, ,*, which bound was improved to ,9/5, ,*, by Borodin, Sanders, and Zhao [1], and to ,5/3,,*, by Sanders and Zhao [7]. We introduce a new parameter k*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that ,c , max {,* + 3,k* + 2, ,* + 14, 3, k* + 6, 18}, and if ,* , 4 and k* , 4, then ,c , ,* + 3,k* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory [source] Improved bounds for the chromatic number of a graphJOURNAL OF GRAPH THEORY, Issue 3 2004S. Louis Hakimi Abstract After giving a new proof of a well-known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres-Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge-cut (V1, V2) in a graph G, together with colorings of ,V1, and ,V2,, what is the least number of colors in a coloring of G which "respects" the colorings of ,V1, and ,V2, ? We give a constructive optimal solution of this problem, and use it to derive a new upper bound for the chromatic number of a graph. As easy corollaries, we obtain several interesting bounds which also appear to be new, as well as classical bounds of Dirac and Ore, and the above mentioned bounds of Matula and Szekeres-Wilf. We conclude by considering two algorithms suggested by our results. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 217,225, 2004 [source] Cubic graphs without cut-vertices having the same path layer matrixJOURNAL OF GRAPH THEORY, Issue 3 2001Andrey A. Dobrynin Abstract The path layer matrix (or path degree sequence) of a graph G contains quantitative information about all possible paths in G. The entry (i,j) of this matrix is the number of paths in G having initial vertex i and length j. It is known that there are cubic graphs on 62 vertices having the same path layer matrix (A. A. Dobrynin. J Graph Theory 17 (1993) 1,4). A new upper bound of 36 vertices for the least order of such cubic graphs is established. This bound is realized by cubic graphs without cut-vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 177,182, 2001 [source] Probabilistic solution and bounds for serial inventory systems with discounted and average costsNAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 6 2007Xiuli Chao Abstract We consider the infinite horizon serial inventory system with both average cost and discounted cost criteria. The optimal echelon base-stock levels are obtained in terms of only probability distributions of leadtime demands. This analysis yields a novel approach for developing bounds and heuristics for optimal inventory control polices. In addition to deriving the known bounds in literature, we develop several new upper bounds for both average cost and discounted cost models. Numerical studies show that the bounds and heuristic are very close to optimal.© 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007 [source] | ||||||||||