On the minimum degree forcing \(F\)-free graphs to be (nearly) bipartite (Q932657): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Miklós Simmonovits / rank | |||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Property / author | |||
Property / author: Miklós Simmonovits / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2007.06.047 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2158274269 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the connection between chromatic number, maximal clique and minimal degree of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3852212 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5567712 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a valence problem in extremal graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of linear graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nearly bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5548826 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3312262 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5689007 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4200109 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5781249 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 13:23, 28 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the minimum degree forcing \(F\)-free graphs to be (nearly) bipartite |
scientific article |
Statements
On the minimum degree forcing \(F\)-free graphs to be (nearly) bipartite (English)
0 references
11 July 2008
0 references
Let \(\beta(G)\) denote the minimum number of edges that can be deleted from \(G\) that results in a bipartite graph, and for a \(3\)-chromatic graph define \(\xi(F)\) to be the maximum \(k\) such that \(F\) can be homomorphically mapped into \(C_k\) for \(k\) odd. This is denoted by \(F \rightarrow C_k\). It is shown that for every \(\alpha, \eta > 0\), there exists an \(n_0\) such that if for every \(F\)-free \(G\), where \(F\) is \(3\)-chromatic, \(G\) has at least \(n_0\) vertices, and \(\delta (G) \geq \left\lfloor (2n)/(\xi(F) + 2) \right\rfloor + \eta n\), then \(\beta(G) \leq \alpha(n^2)\). It is also shown that for every \(\alpha > 0\), there is an \(\overline{\eta}> 0\) and an \(\overline{n}_0\) such that every \(F\)-free graph \(G\) of order \(n \geq \overline{n}_0\) and \(\delta (G) \geq \left\lfloor (2n)/(\xi(F) + 2) \right\rfloor - \overline{\eta} n\) contains a subgraph \(G'\) with at least \(e(G) - \alpha n^2\) edges such that \(G' \rightarrow C_{\xi(F) + 2}\).
0 references
extremal graph theory
0 references
bipartite graphs
0 references
odd cycles
0 references
chromatic number
0 references
0 references