Abstract
Given a graph H, let ƒ(n,H) denote the maximum number of edges not contained in any monochromatic copy of H ina 2-edge-coloring of Kn. The Turan number of a graph H, denoted by ex(n,H), is the maximum number of edges in an n-vertex graph which does not contain H as a subgraph. It is easy to see that f (n, H) ≥ex(n, H) for any H and n. We show that this lower bound is tight for matching-critical graphs including Pertersen graph and vertex- disjoint union of copies of cliques with same order.
| Original language | English |
|---|---|
| Article number | 0253-2778(2020)03-0343-06 |
| Pages (from-to) | 343-348 |
| Number of pages | 6 |
| Journal | Journal of University of Science and Technology of China |
| Volume | 50 |
| Issue number | 3 |
| DOIs | |
| State | Published - Mar 2020 |
Keywords
- Edge coloring
- Matching critical graph
- Monochromatic copy
Fingerprint
Dive into the research topics of 'On the number of edges not covered by monodiromatic copies of a matching-critical graph'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver