A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.     

Fixed point theorems for Reich type contractions on metric spaces with a graph

Let (X,d)$(X,d)$ be a metric space endowed with a graph G$G$ such that the set V(G)$V\left(G\right)$ of vertices of G$G$ coincides with X$X$. We define the notion of G$G$-Reich type maps and obtain a fixed point theorem for such mappings. This extends and subsumes many recent results which were obtained for other contractive type mappings on ordered metric spaces and for cyclic operators.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

Stable extendibility of vector bundles over real projective spaces

Let F$\mathbb{F}$ be either the real number field R$\mathbb{R}$ or the complex number field C$\mathbb{C}$ and RPⁿ${\mathbb{RP}}^n$ the real projective space of dimension n. Theorems A and C in Hemmi and Kobayashi (2008) [2] give necessary and sufficient conditions for a given F$\mathbb{F}$-vector bundle over RPⁿ${\mathbb{RP}}^n$ to be stably extendible to RP^m${\mathbb{RP}}^m$ for every m?n$m?n$. In this paper, we simplify the theorems and apply them to the tangent bundle of RPⁿ${\mathbb{RP}}^n$, its complexification, the normal bundle associated to an immersion of RPⁿ${\mathbb{RP}}^n$ in R^n+r${\mathbb{R}}^{n+r}$(r>0)$(r>0)$, and its complexification. Our result for the normal bundle is a generalization of Theorem A in Kobayashi et al. (2000) [8] and that for its complexification is a generalization of Theorem 1 in Kobayashi and Yoshida (2003) [5].