Title | ||
---|---|---|
Forbidden Properly Edge-Colored Subgraphs that Force Large Highly Connected Monochromatic Subgraphs. |
Abstract | ||
---|---|---|
We consider the connected graphs G that satisfy the following property: If $$n \\gg m \\gg k$$n¿m¿k are integers, then any coloring of the edges of $$K_{n}$$Kn, using m colors, containing no properly colored copy of G, contains a monochromatic k-connected subgraph of order at least $$n - f(G, k, m)$$n-f(G,k,m) where f does not depend on n. If we let $$\\mathscr {G}$$G denote the set of graphs satisfying this statement, we exhibit some infinite families of graphs in $$\\mathscr {G}$$G as well as conjecture that the cycles in $$\\mathscr {G}$$G are precisely those whose lengths are divisible by 3. Our main result is that $$C_{6} \\in \\mathscr {G}$$C6¿G. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/s00373-017-1804-5 | Graphs and Combinatorics |
Keywords | Field | DocType |
Monochromatic Connectivity, Edge-Coloring, Forbidden Subgraph, 6-Cycle | Integer,Topology,Edge coloring,Discrete mathematics,Graph,Colored,Monochromatic color,Combinatorics,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
33 | 4 | 0911-0119 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Robert Katic | 1 | 0 | 0.34 |
Colton Magnant | 2 | 113 | 29.08 |
Pouria Salehi Nowbandegani | 3 | 5 | 4.30 |