✦ LIBER ✦

On 3-colorable planar graphs without short cycles

✍ Scribed by Min Chen; Weifan Wang

Publisher: Elsevier Science
Year: 2008
Tongue: English
Weight: 198 KB
Volume: 21
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2007.10.010

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Planar graph colorings without short mon

Planar graph colorings without short monochromatic cycles

✍ Tomáš Kaiser; Riste Škrekovski 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract It is well known that every planar graph __G__ is 2‐colorable in such a way that no 3‐cycle of __G__ is monochromatic. In this paper, we prove that __G__ has a 2‐coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph __K__~5~ does not admit such a coloring. On

Planar graphs with neither 5-cycles nor

Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable

✍ Oleg V. Borodin; Aleksei N. Glebov 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 561 KB

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

Total Colorings of Planar Graphs without

Total Colorings of Planar Graphs without Small Cycles

✍ Jianfeng Hou; Yan Zhu; Guizhen Liu; Jianliang Wu; Mei Lan 📂 Article 📅 2008 🏛 Springer Japan 🌐 English ⚖ 197 KB

On 3-colorable non-4-choosable planar gr

On 3-colorable non-4-choosable planar graphs

✍ Voigt, M.; Wirth, B. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

An L-list coloring of a graph G is a proper vertex coloring in which every vertex v gets a color from a list L(v) of allowed colors. G is called k-choosable if all lists L(v) have exactly k elements and if G is L-list colorable for all possible assignments of such lists. Verifying conjectures of Erd

Vertex colorings of graphs without short

Vertex colorings of graphs without short odd cycles

✍ Andrzej Dudek; Reshma Ramadurai 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

Motivated by the work of Nešetřil and R ödl on "Partitions of vertices" we are interested in obtaining some quantitative extensions of their result. In particular, given a natural number r and a graph G of order m with odd girth g, we show the existence of a graph H with odd girth at least g and ord