𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on embedding graphs without short cycles

✍ Scribed by Agnieszka Görlich; Monika Pilśniak; Mariusz Woźniak; Irmina A. Zioło

Book ID
108113405
Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
169 KB
Volume
286
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Note on graphs without repeated cycle le
Note on graphs without repeated cycle lengths
✍ Chen, Guantao; Lehel, Jen�; Jacobson, Michael S.; Shreve, Warren E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

In this note we prove that every 2-connected graph of order n with no repeated cycle lengths has at most n + 2(n -2) -1 edges and we show this result is best possible with the correct order of magnitude on √ n. The 2connected case is also used to give a quick proof of Lai's result on the general cas

Choosability of toroidal graphs without
Choosability of toroidal graphs without short cycles
✍ Leizhen Cai; Weifan Wang; Xuding Zhu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 1 views

## Abstract Let __G__ be a toroidal graph without cycles of a fixed length __k__, and χ~__l__~(__G__) the list chromatic number of __G__. We establish tight upper bounds of χ~__l__~(__G__) for the following values of __k__: © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 1–15, 2010.

Coloring Graphs without Short Non-boundi
Coloring Graphs without Short Non-bounding Cycles
✍ S. Fisk; B. Mohar 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 357 KB

It is shown that there is a constant \(c\) such that if \(G\) is a graph embedded in a surface of genus \(g\) (either orientable or non-orientable) and the length of a shortest non-bounding cycle of \(G\) is at least \(c \log (g+1)\), then \(G\) is six-colorable. A similar result holds for three- an