Total chromatic number of unichord-free graphs

A unichord is an edge that is the unique chord of a cycle in a graph. The class C of unichord-free graphs — that is, graphs that do not contain, as an induced subgraph, a cycle with a unique chord — was recently studied by Trotignon and Vuškovi? (2010) [24], who proved strong structure results for these graphs and used these results to solve the recognition and vertex-colouring problems. Machado et al. (2010) [18] determined the complexity of the edge-colouring problem in the class C and in the subclass C^′ obtained from C by forbidding squares. In the present work, we prove that the total-colouring problem is NP-complete when restricted to graphs in C. For the subclass C^′, we establish the validity of the Total Colouring Conjecture by proving that every non-complete {square, unichord}-free graph of maximum degree at least 4 is Type 1.     

A structural theorem on embedded graphs and its application to colorings

In this paper, a Lebesgue type theorem on the structure of graphs embedded in the surface of characteristic σ≤ 0 is given, that generalizes a result of Borodin on plane graphs. As a consequence, it is proved that every such graph without i-circuits for 4 ≤ i ≤ 11 - 3σ is 3-choosable, that offers a new upper bound to a question of Y. Zhao.     

环面图上的一个Lebesgue型定理及其在线性染色中的应用

设c是图G的一个顶点染色, 如果c的任意两个色类都导出一个最大度至多为2的无圈子图,则称c为G的一个无圈染色. 我们首先证明了环面图上的一个Lebesgue 型定理, 作为其应用证明了对任一个围长不小于5 的环面图G, 除非△(G) = 4 而且G有一个子图H使得H的每一个面都是与三个3度点和二个4度点相关的5度面, H一定是(「(△(G))/2」+ 4)- 线性列表可染色的. 这一结果推广和改进了一些已知结论.     

A structural theorem for planar graphs with some applications

In this note, we prove a structural theorem for planar graphs, namely that every planar graph has one of four possible configurations: (1) a vertex of degree 1, (2) intersecting triangles, (3) an edge xy with d(x)+d(y)≤9, (4) a 2-alternating cycle. Applying this theorem, new moderate results on edge choosability, total choosability, edge-partitions and linear arboricity of planar graphs are obtained.     

A sufficient condition for planar graphs with maximum degree 8 to be 9-totally colorable

A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ'(G) is the smallest integer k such that G has a total k-coloring. It is known that if a planar graph G has maximum degree Δ≥ 9, then χ'(G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without a fan of four adjacent 3-cycles, then χ'(G) = 9.     

TheO(n3) algorithm for a special case of the maximum cost-to-time ratio cycle problem and its coherence with an eigenproblem of a matrix

Let twon×n matrices be given, namely a real matrixA=(a_ij) and a (0, 1)-matrixT=(t_ij). For a cyclic permutation=(i ₁,i ₂,...,i _k) of a subset of N={1, 2, ..., n} we define _A;T(), the cost-to-time ratio weight of, as . This paper presents an O(n³) algorithm for finding (A;T)=max _A;T(), the maximum cost-to-time ratio weight of the matricesA andT. Moreover a generalised eigenproblem is proposed.     

A Liouville theorem and blowup behavior for a vector‐valued nonlinear heat equation with no gradient structure

We prove a Liouville theorem for the following heat system whose nonlinearity has no gradient structure: where pq, > 1, p ≥ 1, q ≥ 1, and |p−q| small. We then deduce a localization property and uniform L^∞ estimates of blowup solutions of this system. © 2001 John Wiley & Sons, Inc.     

A unifying theorem for Newton’s method on spaces with a convergence structure

We present a semilocal convergence theorem for Newton’s method (NM) on spaces with a convergence structure. Using our new idea of recurrent functions, we provide a tighter analysis, with weaker hypotheses than before and with the same computational cost as for Argyros (1996, 1997, 1997, 2007) [1], [2], [3] and [5], Meyer (1984, 1987, 1992) [13], [14] and [15]. Numerical examples are provided for solving equations in cases not covered before.     

A decomposition method using a pricing mechanism for min concave cost flow problems with a hierarchical structure

In this paper we develop a decomposition method using a pricing mechanism which has been widely applied to linear and convex programs for a class of nonconvex optimization problems that are min concave cost flow problems under directed, uncapacitated networks with a hierarchical structure.This paper was completed during the author's stay supported by a Sophia lecturing-research Grant at Sophia University, Tokyo, Japan.     

双正则函数向量的带Haseman位移带共轭值的线性及非线性边值问题

首先利用积分方程的方法和Arzela-Ascoli定理讨论了实Clifford分析中双正则函数向量的带Haseman位移带共轭值的非线性边值问题解的存在性及其积分表达式,其次利用压缩映射原理解决了其线性边值问题解的存在唯一性及其积分表达式.     

Algorithms for solving discrete optimal control problems with infinite time horizon and determining minimal mean cost cycles in a directed graph as decision support tool

Time-discrete systems with a finite set of states are considered. Discrete optimal control problems with infinite time horizon for such systems are formulated. We introduce a certain graph-theoretic structure to model the transitions of the dynamical system. Algorithms for finding the optimal stationary control parameters are presented. Furthermore, we determine the optimal mean cost cycles. This approach can be used as a decision support strategy within such a class of problems; especially so-called multilayered decision problems which occur within environmental emission trading procedures can be modelled by such an approach.     

A theorem on S-shaped bifurcation curve for a positone problem with convex-concave nonlinearity and its applications to the perturbed Gelfand problem

We study the bifurcation curve and exact multiplicity of positive solutions of the positone problem

     

A structure theorem for posets admitting a “strong” chain partition:: A generalization of a conjecture of Daykin and Daykin (with connections to probability correlation inequalities)

Suppose a finite poset P is partitioned into three non-empty chains so that, whenever p, q∈P lie in distinct chains and p<q, then every other element of P is either above p or below q.In 1985, the following conjecture was made by David Daykin and Jacqueline Daykin: such a poset may be decomposed into an ordinal sum of posets such that, for 1?i?n, one of the following occurs:

(1)

R_i is disjoint from one of the chains of the partition; or

(2)

if p, q∈R_i are in distinct chains, then they are incomparable.

The conjecture is related to a question of R. L. Graham's concerning probability correlation inequalities for linear extensions of finite posets.In 1996, a proof of the Daykin-Daykin conjecture was announced (by two other mathematicians), but their proof needs to be rectified.In this note, a generalization of the conjecture is proven that applies to finite or infinite posets partitioned into a (possibly infinite) number of chains with the same property. In particular, it is shown that a poset admits such a partition if and only if it is an ordinal sum of posets, each of which is either a width 2 poset or else a disjoint sum of chains. A forbidden subposet characterization of these partial orders is also obtained.