Győri, Ervin and Kensell, Scott and Tompkins, Casey (2016) Making a C6C6-free graph C4C4-free and bipartite. DISCRETE APPLIED MATHEMATICS, 209. pp. 133-136. ISSN 0166-218X
![[img]](http://real.mtak.hu/style/images/fileicons/text.png) |
Text
1_s2.0_S0166218X15002942_main_u.pdf - Published Version Restricted to Registered users only Download (356kB) | Request a copy |
|
|
Text
44158.pdf - Submitted Version Download (175kB) | Preview |
Official URL: http://dx.doi.org/10.1016/j.dam.2015.06.008
Abstract
We show that every C6C6-free graph GG has a C4C4-free, bipartite subgraph with at least 3e(G)/83e(G)/8 edges. Our proof is probabilistic and uses a theorem of Füredi et al. (2006) on C6C6-free graphs.
| Item Type: | Article |
|---|---|
| Additional Information: | Available online 13 July 2015 9th International Colloquium on Graph Theory and Combinatorics, 2014, Grenoble |
| Uncontrolled Keywords: | 4-CYCLES; 6-cycles; Bipartite subgraphs; Extremal graphs; Graph theory |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 03 Jan 2017 08:55 |
| Last Modified: | 11 Jan 2017 01:15 |
| URI: | http://real.mtak.hu/id/eprint/44158 |
Actions (login required)
 |
Edit Item |
