✦ LIBER ✦

Highly connected monochromatic subgraphs of multicolored graphs

✍ Scribed by Henry Liu; Robert Morris; Noah Prince

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 786 KB
Volume: 61
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20365

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider the following question of Bollobás: given an r‐coloring of E(K~n~), how large a k‐connected subgraph can we find using at most s colors? We provide a partial solution to this problem when s=1 (and n is not too small), showing that when r=2 the answer is n−2__k__+2, when r=3 the answer is ⌊(n−k)/2⌋+1 or ⌈(n−k)/2⌉+1, and when r−1 is a prime power then the answer lies between n/(r−1)−11(k^2^−k)r and (n−k+1)/(r−1)+r. The case s≥2 is considered in a subsequent paper (Liu et al.[6]), where we also discuss some of the more glaring open problems relating to this question. © 2009 Wiley Periodicals, Inc. J. Graph Theory 61: 22‐44, 2009

📜 SIMILAR VOLUMES

Connected Spanning Subgraphs of 3-Connec

Connected Spanning Subgraphs of 3-Connected Planar Graphs

✍ Hikoe Enomoto; Tadashi Iida; Katsuhiro Ota 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 339 KB

2-Connected Spanning Subgraphs of Planar

2-Connected Spanning Subgraphs of Planar 3-Connected Graphs

✍ D.W. Barnette 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 278 KB

We prove that every planar 3-connected graph has a 2-connected spanning subgraph of maximum valence 15 . We give an example of a planar 3 -connected graph with no spanning 2-connected subgraph of maximum valence five. i) 1994 Academic Press, Inc.

Spanning even subgraphs of 3-edge-connec

Spanning even subgraphs of 3-edge-connected graphs

✍ Bill Jackson; Kiyoshi Yoshimoto 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB

## Abstract By Petersen's theorem, a bridgeless cubic graph has a 2‐factor. H. Fleischner extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has a spanning even subgraph. Our main result is that, under the stronger hypothesis of 3‐edge‐connec

Typical Subgraphs of 3- and 4-Connected

Typical Subgraphs of 3- and 4-Connected Graphs

✍ B. Oporowski; J. Oxley; R. Thomas 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 773 KB

Pancyclicity of 3-connected graphs: Pair

Pancyclicity of 3-connected graphs: Pairs of forbidden subgraphs

✍ Ronald J. Gould; Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB

## Abstract We characterize all pairs of connected graphs {__X__, __Y__} such that each 3‐connected {__X__, __Y__}‐free graph is pancyclic. In particular, we show that if each of the graphs in such a pair {__X__, __Y__} has at least four vertices, then one of them is the claw __K__~1,3~, while the

On partitioning the edges of graphs into

On partitioning the edges of graphs into connected subgraphs

✍ M. Jünger; G. Reinelt; W. R. Pulleyblank 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 559 KB

For any positive integer s, an s-partition of a graph G = ( ! -( €I is a partition of E into El U E2 U U E k, where 14 = s for 1 I i 5 k -1 and 1 5 1 4 1 5 s and each €; induces a connected subgraph of G. We prove (i) if G is connected, then there exists a 2-partition, but not neces-(ii) if G is 2-e