تقرير
On the difference between the chromatic and cochromatic number
| العنوان: | On the difference between the chromatic and cochromatic number |
|---|---|
| المؤلفون: | Steiner, Raphael |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C15, 05C69 |
| الوصف: | The cochromatic number $\zeta(G)$ of a graph $G$ is the smallest number of colors in a vertex-coloring of $G$ such that every color class forms an independent set or a clique. In three papers written around 1990, Erd\H{o}s, Gimbel and collaborators raised several open problems regarding the relationship of the chromatic and cochromatic number of a graph. In this short note, we address several of these problems, in particular -we disprove a conjecture of Erd\H{o}s, Gimbel and Straight from 1988, -answer negatively a problem posed by Erd\H{o}s and Gimbel in 1993, and -give positive evidence for a 1000\$--question of Erd\H{o}s and Gimbel. Comment: 7 pages, updated and extended version |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2408.02400 |
| رقم الأكسشن: | edsarx.2408.02400 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |