Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

Construction of uniquely H‐colorable graphs

We shall prove that for any graph H that is a core, if χ(G) is large enough, then H × G is uniquely H‐colorable. We also give a new construction of triangle free graphs, which are uniquely n‐colorable. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 1–6, 1999     

The Hamilton–Waterloo Problem for ‐Factors and ‐Factors

The Hamilton–Waterloo problem asks for a 2‐factorization of (for v odd) or minus a 1‐factor (for v even) into ‐factors and ‐factors. We completely solve the Hamilton–Waterloo problem in the case of C₃‐factors and ‐factors for .     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

Explicit 2-Factorisations of the Odd Graph

In this note we show how 1-factors in the middle two layers of the discrete cube can be used to construct 2-factors in the Odd graph (the Kneser graph of (k − 1)-sets from a (2k − 1)-set). In particular, we use the lexical matchings of Kierstead and Trotter, and the modular matchings of Duffus, Kierstead and Snevily, to give explicit constructions of two different 2-factorisations of the Odd graph. This revised version was published online in September 2006 with corrections to the Cover Date.     

关于奇强协调图的一些结果

对于一个(p,q)-图G,如果存在一个单射f:V(G)→{0,1,…,2q-1},使得边标号集合{f(uv)|uv∈E(G)}={1,3,5,…,2q-1},其中边标号为f(uv)=f(u)+f(v),那么称G是奇强协调图,并称f是G的一个奇强协调标号.通过研究若干奇强协调图,得出一些奇强协调图的性质.     

Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

伪完全二分图PK_(n,n)奇优美标号的计算机实现

给出了伪完全二分图PK_(n,n)的定义及性质,提出了该类图的奇优美标号算法,证明了算法的正确性及时间复杂度,从而证明了伪完全二分图的奇优美性.并给出了伪完全二分图PK_(n,n),当n=3,4,5的一种标号方法.     

Some extensions of the improved modified Gauss–Seidel iterative method for H‐matrices

In this paper, first we present a convergence theorem of the improved modified Gauss–Seidel iterative method, referred to as the IMGS method, for H‐matrices and compare the range of parameters α_i with that of the parameter ω of the SOR iterative method. Then with a more general splitting, the convergence analysis of this method for an H‐matrix and its comparison matrix is given. The spectral radii of them are also compared. Copyright © 2006 John Wiley & Sons, Ltd.     

Odd‐sized partitions of Russell‐sets

In the setting of ZF, i.e., Zermelo–Fraenkel set theory without the Axiom of Choice (AC), we study partitions of Russell‐sets into sets each with exactly n elements (called n ‐ary partitions), for some integer n. We show that if n is odd, then a Russell‐set X has an n ‐ary partition if and only if |X | is divisible by n. Furthermore, we establish that it is relative consistent with ZF that there exists a Russell‐set X such that |X | is not divisible by any finite cardinal n > 1 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On hyper‐torre isols

In this paper we present a contribution to a classical result of E. Ellentuck in the theory of regressive isols. E. Ellentuck introduced the concept of a hyper‐torre isol, established their existence for regressive isols, and then proved that associated with these isols a special kind of semi‐ring of isols is a model of the true universal‐recursive statements of arithmetic. This result took on an added significance when it was later shown that for regressive isols, the property of being hyper‐torre is equivalent to being hereditarily odd‐even. In this paper we present a simplification to the original proof for establishing that equivalence. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Global sharp interface limit of the Hele–Shaw–Cahn–Hilliard system

In this paper, we focus on a diffuse interface model named by Hele–Shaw–Cahn–Hilliard system, which describes a two‐phase Hele–Shaw flow with matched densities and arbitrary viscosity contrast in a bounded domain. The diffuse interface thickness is measured by ? , and the mobility coefficient (the diffusional Peclet number) is ? ^α . We will prove rigorously that the global weak solutions of the Hele–Shaw–Cahn–Hilliard system converge to a varifold solution of the sharp interface model as ? →0 in the case of 0≤α  < 1. Copyright © 2016 John Wiley & Sons, Ltd.     

An Extension of Set-Valued Contraction Principle for Mappings on a Metric Space with a Graph and Application

In this paper, we obtain an existence theorem for fixed points of contractive set-valued mappings on a metric space endowed with a graph. This theorem unifies and extends several fixed point theorems for mappings on metric spaces and for mappings on metric spaces endowed with a graph. As an application, we obtain a theorem on the convergence of successive approximations for some linear operators on an arbitrary Banach space. This result yields the well-known Kelisky–Rivlin theorem on iterates of the Bernstein operators on C[0,1].     

Topological Constructions in the o–Graph Calculus

Benedetti and Petronio developed in [1] a so called o–Graph Calculus, where a compact oriented 3–manifold with nonempty boundary could be described by a quadrivalent graph together with some extra structure. In this paper, we will show how topological constructions such as puncturing, connected sums, attaching handles, closing boundary components and product and mapping tori constructions can be translated into the o–graph calculus.     

An Upper Bound for the Excessive Index of an r‐Graph

We construct a family of r‐graphs having a minimum 1‐factor cover of cardinality (disproving a conjecture of Bonisoli and Cariolaro, Birkhäuser, Basel, 2007, 73–84). Furthermore, we show the equivalence between the statement that is the best possible upper bound for the cardinality of a minimum 1‐factor cover of an r‐graph and the well‐known generalized Berge–Fulkerson conjecture.     

On Extension and Continuity of p–Additive Functions

In this paper we prove some properties of p–additive functions as well as p–additive set–valued functions.     

An Asymptotic Version of the Multigraph 1‐Factorization Conjecture

We give a self‐contained proof that for all positive integers r and all , there is an integer such that for all any regular multigraph of order 2n with multiplicity at most r and degree at least is 1‐factorizable. This generalizes results of Perkovi? and Reed (Discrete Math 165/166 (1997), 567–578) and Plantholt and Tipnis (J London Math Soc 44 (1991), 393–400).     

Graph diameter in long‐range percolation

We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|^?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)^Δ+o(1) where Δ^?1 := log₂(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r^1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011