On the chromatic number of (P₅, K_2,t)-free graphs

详细信息    查看全文

• 作者：Christoph Brause^a ; ^{brause@math.tu-freiberg.de" class="auth_mail" title="E-mail the corresponding author} ; Trung Duy Doan^a ; ^b ; ^{trungdoanduy@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Ingo Schiermeyer^a ; ^{ingo.schiermeyer@tu-freiberg.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：chromatic number ; χ-binding function ; P5P5-free graphs
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：55
• 期：Complete
• 页码：127-130
• 全文大小：180 K

文摘

In this paper we study the chromatic number of (P₅$P_5$, K_2,t$K_{2,t}$)-free graphs with t≥2$t\ge 2$. It is still an open question whether there are polynomial (χ  -binding) functions f_k$f_k$ for k≥5$k\ge 5$ such that every 132b4b8e3f" title="Click to view the MathML source">P_k$P_k$-free graph G   satisfies χ(G)≤f_k(ω(G))$\chi (G)\le f_k(\omega (G))$, where 132b4b8e3f" title="Click to view the MathML source">P_k$P_k$ is an induced path on k   vertices. Our main result is that every (P₅$P_5$, K_2,t$K_{2,t}$)-free graph G admits a polynomial χ-binding function. Moreover, we will present polynomial χ  -binding functions for several other subclasses of P₅$P_5$-free graphs.