A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

定逆序数的n元数码置换个数的一种方法

一个确定的n元数码的排列,其道序数是不难求得的;反之,“已知逆序数,求有多少个n元置换”的问题要复杂得多。从最小数码的位置着手,充分利用逆序数是定数,给出一种解决此问题的新方法——最小数码定位法。此法通俗易懂,由此得到了逆序数为k(k=1,2,3……c_n~2)的n元数码的置换个数的一个递推公式:q_k(n)=1+q_1(n-l)+q_2(n-1)+q_3(n-1)+…+q_k(n-1)。     

4一致C-超图的最小边数问题

研究了上色数为3的4一致C-超图的最小边数问题，并给出了上色数为3的4一致C-超图的最小边数的一个上界．     

伞花木染色体核型的研究

本文首次报道了国家二级保护植物伴花木（无患子科）的染色体数目，并对其核型进行了分析，结果表明：该种染色体的核型公式为：Ｋ（２ｎ）＝２２＝１６ｍ＋６ｓｍ，染色体属较对称的“２Ｂ”型。     

C^n中子空间之间极端主角的一些应用

本文给出了Ｃ＾ｎ中子空间之间最大和最小主角在矩阵逼近，投影算子的扰动分析，群逆以及Ｏｒａｘｉｎ逆的扰动估计，条件数理论，Ｂｏｔｔ－Ｄｕｆｆｉｎ系统扰动分析中一些应用。     

Proof of a conjecture on irredundance perfect graphs

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002     

猜想M(2k,k+1)=3k-1+[(k-1)/2]的反例

Brualdi与Jung在[1]中研究了一类具有固定线和k的n×n矩阵上的最大跳跃数M(n,k),并提出猜想M(2k, k + 1) = 3k - 1 + [(k-1)/2].本文给出了这一猜想的两个反例．     

若干图类的邻强边染色

研究了若干图类的邻强边染色 .利用在图中添加辅助点和边的方法 ,构造性的证明了对于完全图 Kn和路 Lm 的笛卡尔积图 Kn× Lm,有χ′as(Kn× Lm) =△ (Kn× Lm) +1 ,其中△ (Kn× Lm)和χ′as(Kn× Lm)分别表示图 Kn× Lm的最大度和邻强边色数 .同理验证了 n阶完全图 Kn的广义图 K(n,m)满足邻强边染色猜想 .     

LehmerDH数在模p剩余系的分布

设 p≥ 3为素数 ,集合A ={a|1≤a 相似文献   

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．