Coloring (gem, co‐gem)‐free graphs

A gem is a graph that consists of a path on four vertices plus a vertex adjacent to all four vertices of the path. A co‐gem is the complement of a gem. We prove that every (gem, co‐gem)‐free graph G satisfies the inequality (a special case of a conjecture of Gyárfás) and the inequality (a special case of a conjecture of Reed). Moreover, we give an ‐time algorithm that computes the chromatic number of any (gem, co‐gem)‐free graph with n vertices, while the existing algorithm in the literature takes .     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

On the Roots of σ‐Polynomials

Given a graph G of order n, the σ‐polynomial of G is the generating function where is the number of partitions of the vertex set of G into i nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti (Trans Am Math Soc 332 (1992), 729–756) proved that σ‐polynomials of graphs with chromatic number at least had all real roots, and conjectured the same held for chromatic number . We affirm this conjecture.     

Perfect coloring and linearly χ‐bound P6‐free graphs

We derive decomposition theorems for P₆, K₁ + P₄‐free graphs, P₅, K₁ + P₄‐free graphs and P₅, K₁ + C₄‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, P_n (C_n) denotes the path (cycle) on n vertices and K₁ + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal χ‐binding function for P₅, C₄‐free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 11 , Discrete Math, 146, 33–44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293–306, 2007     

Amalgams and χ‐Boundedness

A class of graphs is hereditary if it is closed under isomorphism and induced subgraphs. A class of graphs is χ‐bounded if there exists a function such that for all graphs , and all induced subgraphs H of G, we have that . We prove that proper homogeneous sets, clique‐cutsets, and amalgams together preserve χ‐boundedness. More precisely, we show that if and are hereditary classes of graphs such that is χ‐bounded, and such that every graph in either belongs to or admits a proper homogeneous set, a clique‐cutset, or an amalgam, then the class is χ‐bounded. This generalizes a result of [J Combin Theory Ser B 103(5) (2013), 567–586], which states that proper homogeneous sets and clique‐cutsets together preserve χ‐boundedness, as well as a result of [European J Combin 33(4) (2012), 679–683], which states that 1‐joins preserve χ‐boundedness. The house is the complement of the four‐edge path. As an application of our result and of the decomposition theorem for “cap‐free” graphs from [J Graph Theory 30(4) (1999), 289–308], we obtain that if G is a graph that does not contain any subdivision of the house as an induced subgraph, then .     

χ‐bounds,operations, and chords

A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most colors, where ω is the maximum number of pairwise adjacent vertices in G.     

On effective σ‐boundedness and σ‐compactness

We prove several dichotomy theorems which extend some known results on σ‐bounded and σ‐compact pointsets. In particular we show that, given a finite number of $\Delta ^{1}_{1}$ equivalence relations $\mathrel {\mathsf {F}}_1,\dots ,\mathrel {\mathsf {F}}_n$, any $\Sigma ^{1}_{1}$ set A of the Baire space either is covered by compact $\Delta ^{1}_{1}$ sets and lightface $\Delta ^{1}_{1}$ equivalence classes of the relations $\mathrel {\mathsf {F}}_i$, or A contains a superperfect subset which is pairwise $\mathrel {\mathsf {F}}_i$‐inequivalent for all i = 1, …, n. Further generalizations to $\Sigma ^{1}_{2}$ sets A are obtained.     

σ‐short Boolean algebras

We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach‐Mazur Boolean game. A σ‐short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ‐short Boolean algebras and study properties of σ‐short Boolean algebras. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Order plus size of τ‐critical graphs

Let $G=\left(V,E\right)$ be a $\tau$‐critical graph with $\tau \left(G\right)=t$. Erd?s and Gallai proved that $\mid V\mid \le 2t$ and the bound $\mid E\mid \le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)$ was obtained by Erd?s, Hajnal, and Moon. We give here the sharp combined bound $\mid E\mid +\mid V\mid \le \left(\genfrac{}{}{0ex}{}{t+2}{2}\right)$ and find all graphs with equality.     

A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω

In 1998 the second author proved that there is an such that every graph satisfies . The first author recently proved that any graph satisfying contains a stable set intersecting every maximum clique. In this note, we exploit the latter result to give a much shorter, simpler proof of the former. Working from first principles, we omit only some five pages of proofs of known intermediate results (which appear in an extended version of this paper), and the proofs of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality.     

Characterization of g∞,σ‐integral operators

The application of the general tensor norms theory of Defant and Floret to the ideal of (p, σ)‐absolutely continuous operators of Matter, 0 < σ < 1, 1 ≤ p < ∞ leads to the study of g_p′,σ‐nuclear and g_p′,σ‐integral operators. Characterizations of such operators has been obtained previously in the case p > 1. In this paper we characterize the g_∞,σ‐nuclear and g_∞,σ‐integral operators by the existence of factorizations of some special kinds. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Admissible perturbations of α‐ψ‐pseudocontractive operators: convergence theorems

We prove some convergence theorems for α‐ψ‐pseudocontractive operators in real Hilbert spaces, by using the concept of admissible perturbation. Our results extend and complement some theorems in the existing literature. Copyright © 2016 John Wiley & Sons, Ltd.     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Index sets for ω‐languages

An ω‐language is a set of infinite sequences (words) on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the languages, may enumerated as P₀, P₁, … and then an index set associated to a given property R (such as finiteness) of languages is just the set of e such that P_e has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language.     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

Hierarchies in φ‐spaces and applications

We establish some results on the Borel and difference hierarchies in φ‐spaces. Such spaces are the topological counterpart of the algebraic directed‐complete partial orderings. E.g., we prove analogs of the Hausdorff Theorem relating the difference and Borel hierarchies and of the Lavrentyev Theorem on the non‐collapse of the difference hierarchy. Some of our results generalize results of A. Tang for the space Pω. We also sketch some older applications of these hierarchies and present a new application to the question of characterizing the ω‐ary Boolean operations generating a given level of the Wadge hierarchy from the open sets. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A (T,ψ)‐ψe decoupled scheme for a time‐dependent multiply‐connected eddy current problem

The aim of this paper is to develop a fully discrete ( T ,ψ)‐ψ_e finite element decoupled scheme to solve time‐dependent eddy current problems with multiply‐connected conductors. By making ‘cuts’ and setting jumps of ψ_e across the cuts in nonconductive domain, the uniqueness of ψ_e is guaranteed. Distinguished from the traditional T ‐ ψ method, our decoupled scheme solves the potentials T and ψ‐ ψ_e separately in two different simple equation systems, which avoids solving a saddle‐point equation system and leads to a remarkable reduction in computational efforts. The energy‐norm error estimate of the fully discrete decoupled scheme is provided. Finally, the scheme is applied to solve two benchmark problems—TEAM Workshop Problems 7 and IEEJ model. Copyright © 2013 John Wiley & Sons, Ltd.     

Convex‐round graphs are circular‐perfect

We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round graphs are circular‐perfect, a concept introduced recently by Zhu [10]. Secondly, we characterize maximal K_r‐free convex‐round graphs and show that they can be obtained from certain circular cliques in a simple fashion. Our proofs rely on several structural properties of convex‐round graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 182–194, 2002     

ω‐saturated quasi‐minimal models of Th(ℚω, +, σ, 0)

We show that (ℚ^ω, +, σ, 0) is a quasi-minimal torsion-free divisible abelian group. After discussing the axiomatization of the theory of this structure, we present its ω-saturated quasi-minimal model. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

ω‐categorical weakly o‐minimal expansions of Boolean lattices

We study ω‐categorical weakly o‐minimal expansions of Boolean lattices. We show that a structure ?? = (A,≤, ?) expanding a Boolean lattice (A,≤) by a finite sequence I of ideals of A closed under the usual Heyting algebra operations is weakly o‐minimal if and only if it is ω‐categorical, and hence if and only if A/I has only finitely many atoms for every I ∈ ?. We propose other related examples of weakly o‐minimal ω‐categorical models in this framework, and we examine the internal structure of these models.