A note on Brooks' theorem for triangle-free graphs
A note on Brooks' theorem for triangle-free graphs
复制标题
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
B. Randerath;I. Schiermeyer
中科院分区：
文献类型：
--
作者：
B. Randerath;I. Schiermeyer
对于无三角形图类，布鲁克斯定理可以用禁止诱导子图来重述，即设 G 是无三角形且无 K1,r+1 的图。则 G 是 r 可色的，除非 G 同构于奇数环或最多有两个顶点的完全图。在这篇文章中，我们提出了对无三角形和无遮阳图的布鲁克斯定理的改进。这里，r-遮阳伞（r ≥ 3）是一颗星形 K1,r，其中一个分支被细分。图着色理论的一个经典结果是 Brooks 定理 [2]，断言每个图 G 都是 (Δ(G))-可着色的，除非 G 同构于奇循环或完全图。 Bryant [3] 通过以下循环特征和完整图简化了该证明。因此，他强调了布鲁克斯定理中循环和完全图的特殊作用。在这里，我们给出了这个表征的新的基本证明。
For the class of triangle-free graphs Brooks’ Theorem can be restated in terms of forbidden induced subgraphs, i.e. let G be a triangle-free and K1,r+1-free graph. Then G is r-colourable unless G is isomorphic to an odd cycle or a complete graph with at most two vertices. In this note we present an improvement of Brooks’ Theorem for triangle-free and rsunshade-free graphs. Here, an r-sunshade (with r ≥ 3) is a star K1,r with one branch subdivided. A classical result in graph colouring theory is the theorem of Brooks [2], asserting that every graph G is (∆(G))-colourable unless G is isomorphic to an odd cycle or a complete graph. Bryant [3] simplified this proof with the following characterization of cycles and complete graphs. Thereby he highlights the exceptional role of the cycles and complete graphs in Brooks’ Theorem. Here we give a new elementary proof of this characterization.