𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Planar graph colorings without short monochromatic cycles

✍ Scribed by Tomáš Kaiser; Riste Škrekovski

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
126 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 the other hand, we extend the result to K~5~‐minor‐free graphs. There are planar graphs with the property that each of their 2‐colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 25–38, 2004

📜 SIMILAR VOLUMES

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

Monochromatic cycle partitions of edge-c
Monochromatic cycle partitions of edge-colored graphs
✍ Gábor N. Sárközy 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 88 KB 👁 1 views

In this article we study the monochromatic cycle partition problem for non-complete graphs. We consider graphs with a given independence number (G) = . Generalizing a classical conjecture of Erd" os, Gyárfás and Pyber, we conjecture that if we r-color the edges of a graph G with (G) = , then the ver

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

Acyclic 5-choosability of planar graphs
Acyclic 5-choosability of planar graphs without adjacent short cycles
✍ O. V. Borodin; A. O. Ivanova 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 1 views

The conjecture on acyclic 5-choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4-cycles. We prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cy

Planar Graphs Without Cycles of Specific
Planar Graphs Without Cycles of Specific Lengths
✍ G. Fijavž; M. Juvan; B. Mohar; R. Škrekovski 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 208 KB

It is easy to see that planar graphs without 3-cycles are 3-degenerate. Recently, it was proved that planar graphs without 5-cycles are also 3-degenerate. In this paper it is shown, more surprisingly, that the same holds for planar graphs without 6-cycles.

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.