✦ LIBER ✦

Vertex colorings of graphs without short odd cycles

✍ Scribed by Andrzej Dudek; Reshma Ramadurai

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 118 KB
Volume: 68
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20557

No coin nor oath required. For personal study only.

✦ Synopsis

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 order that is polynomial in m such that every r-coloring of the vertices of H yields a monochromatic and induced copy of G. ᭧ 2010 Wiley

📜 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

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

Short odd cycles in 4-chromatic graphs

✍ Nilli, A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 3 views

It is shown that any 4-chromatic graph on n vertices contains an odd cycle of length smaller than √ 8n.

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.

Vertex-distinguishing edge colorings of

Vertex-distinguishing edge colorings of graphs

✍ P. N. Balister; O. M. Riordan; R. H. Schelp 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB 👁 1 views

Homomorphisms of graphs into odd cycles

✍ A. M. H. Gerards 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB