On Monochromatic Subgraphs of Edge-Colored Complete Graphs

• Autorzy: Eric Andrews , Futaba Fujie , Kyle Kolasinski , Chira Lumduanhom , Adam Yusko
• Języki publikacji: EN

Abstrakty

EN

In a red-blue coloring of a nonempty graph, every edge is colored red or blue. If the resulting edge-colored graph contains a nonempty subgraph G without isolated vertices every edge of which is colored the same, then G is said to be monochromatic. For two nonempty graphs G and H without isolated vertices, the mono- chromatic Ramsey number mr(G,H) of G and H is the minimum integer n such that every red-blue coloring of Kn results in a monochromatic G or a monochromatic H. Thus, the standard Ramsey number of G and H is bounded below by mr(G,H). The monochromatic Ramsey numbers of graphs belonging to some common classes of graphs are studied. We also investigate another concept closely related to the standard Ram- sey numbers and monochromatic Ramsey numbers of graphs. For a fixed integer n ≥ 3, consider a nonempty subgraph G of order at most n con- taining no isolated vertices. Then G is a common monochromatic subgraph of Kn if every red-blue coloring of Kn results in a monochromatic copy of G. Furthermore, G is a maximal common monochromatic subgraph of Kn if G is a common monochromatic subgraph of Kn that is not a proper sub- graph of any common monochromatic subgraph of Kn. Let S(n) and S*(n) be the sets of common monochromatic subgraphs and maximal common monochromatic subgraphs of Kn, respectively. Thus, G ∈ S(n) if and only if R(G,G) = mr(G,G) ≤ n. We determine the sets S(n) and S*(n) for 3 ≤ n ≤ 8.

Słowa kluczowe

EN

Ramsey number; monochromatic Ramsey number; common monochromatic subgraph; maximal common monochromatic subgraph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 1
• Strony: 5-22

Daty

wydano

2014-02-01

online

2014-02-14

Twórcy

autor

Eric Andrews

• Department of Mathematics Western Michigan University Kalamazoo, MI 49008 USA

autor

Futaba Fujie

• Graduate School of Mathematics Nagoya University Nagoya, Japan 464-8602

autor

Kyle Kolasinski

• Department of Mathematics Western Michigan University Kalamazoo, MI 49008 USA

autor

Chira Lumduanhom

• Department of Mathematics Western Michigan University Kalamazoo, MI 49008 USA

autor

Adam Yusko

• Department of Mathematics Western Michigan University Kalamazoo, MI 49008 USA

Bibliografia

• [1] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (Chapman and Hall/CRC, Boca Raton, FL., 2010).
• [2] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2011) DS1.

Identyfikatory

DOI

10.7151/dmgt.1725