A lower bound on the independence number of a graph in terms of degrees and local clique sizes

详细信息    查看全文

• 作者：C. Brause^a ; ^{brause@math.tu-freiberg.de" class="auth_mail" title="E-mail the corresponding author} ; B. Randerath^b ; ^{hubert.randerath@fh-koeln.de" class="auth_mail" title="E-mail the corresponding author} ; D. Rautenbach^c ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author} ; I. Schiermeyer^a ; ^{schiermeyer@math.tu-freiberg.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Independent set ; Chromatic number ; Degree ; Clique
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 August 2016
• 年：2016
• 卷：209
• 期：Complete
• 页码：59-67
• 全文大小：385 K

文摘

Caro and Wei independently showed that the independence number 954&_mathId=si1.gif&_user=111111111&_pii=S0166218X15002954&_rdoc=1&_issn=0166218X&md5=4915fa2c0869222d05b68b16490ced43" title="Click to view the MathML source">α(G)$\alpha \left(G\right)$ of a graph 954&_mathId=si2.gif&_user=111111111&_pii=S0166218X15002954&_rdoc=1&_issn=0166218X&md5=872bb95e08a41e3c0df6201658394685" title="Click to view the MathML source">G$G$ is at least 954&_mathId=si3.gif&_user=111111111&_pii=S0166218X15002954&_rdoc=1&_issn=0166218X&md5=cc222a40abba0a751e6fab6cd013abf8">954-si3.gif">${\sum }_{u\in V\left(G\right)}\frac{1}{d_G\left(u\right)+1}$. In the present paper we conjecture the stronger bound 954&_mathId=si4.gif&_user=111111111&_pii=S0166218X15002954&_rdoc=1&_issn=0166218X&md5=5cde72255038865536398ed5925815e6">954-si4.gif">$\alpha \left(G\right)\ge {\sum }_{u\in V\left(G\right)}\frac{2}{d_G\left(u\right)+{\omega }_G\left(u\right)+1}$ where 954&_mathId=si5.gif&_user=111111111&_pii=S0166218X15002954&_rdoc=1&_issn=0166218X&md5=fee7f12fd5c7f8f3aff562ed5dc275e3" title="Click to view the MathML source">ω_G(u)${\omega }_G\left(u\right)$ is the maximum order of a clique of 954&_mathId=si2.gif&_user=111111111&_pii=S0166218X15002954&_rdoc=1&_issn=0166218X&md5=872bb95e08a41e3c0df6201658394685" title="Click to view the MathML source">G$G$ that contains the vertex 954&_mathId=si7.gif&_user=111111111&_pii=S0166218X15002954&_rdoc=1&_issn=0166218X&md5=39af70f04ab0a7272cfb0df7a30f8446" title="Click to view the MathML source">u$u$. We discuss the relation of our conjecture to recent conjectures and results concerning the independence number and the chromatic number. Furthermore, we prove our conjecture for perfect graphs and for graphs of maximum degree at most 4.