تقرير
Density of $3$-critical signed graphs
| العنوان: | Density of $3$-critical signed graphs |
|---|---|
| المؤلفون: | Beaudou, Laurent, Haxell, Penny, Nurse, Kathryn, Sen, Sagnik, Wang, Zhouningxin |
| سنة النشر: | 2023 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | We say that a signed graph is $k$-critical if it is not $k$-colorable but every one of its proper subgraphs is $k$-colorable. Using the definition of colorability due to Naserasr, Wang, and Zhu that extends the notion of circular colorability, we prove that every $3$-critical signed graph on $n$ vertices has at least $\frac{3n-1}{2}$ edges, and that this bound is asymptotically tight. It follows that every signed planar or projective-planar graph of girth at least $6$ is (circular) $3$-colorable, and for the projective-planar case, this girth condition is best possible. To prove our main result, we reformulate it in terms of the existence of a homomorphism to the signed graph $C_{3}^*$, which is the positive triangle augmented with a negative loop on each vertex. Comment: 27 pages, 12 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2309.04450 |
| رقم الأكسشن: | edsarx.2309.04450 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |