On some extremal problems in graph theory
From MaRDI portal
Publication:2396159
Der Verf. beweist, daß für eine genügend große Konstante \(c\) jeder Graph \(G\) mit \(n\) Punkten und \(cn^{3/2}\) Kanten ein Sechseck \(x_1,x_2,x_3,x_4,x_5,x_6\) enthält und dazu noch einen siebenten Punkt \(y\), der mit \(x_1,x_3\) und \(x_5\) verbunden ist. Würde \(G\) auch einen mit \(x_2,x_4\) und \(x_6\) verbundenen Punkt \(z\) enthalten, so wäre in \(G\) auch das Kantennetz eines Würfels enthalten --- doch dieses Problem bleibt auch weiterhin offen. Verf. beweist in vorliegender Arbeit eigentlich den folgenden allgemeineren Satz: Sei \(n>n_0(k)\) und \(G\) ein Graph mit \(n\) Punkten und \(10 \cdot [k^{1/2}n^{3/2}]\) Kanten dann enthält \(G\) einen Weg \(\{x_1,y_1,x_2,y_2,...,x_k,y_k,x_{k+1}\}\) sowie die Kanten \((x_1,y_i)\) und \((y_1,x_j)\) für \(2\leq i \leq k\) und \(3\leq j\leq k+1\). Der Fall \(k=3\) enthält den oben genannten Satz.
Recommendations
Cites work
Cited in
(81)- Maximum bipartite subgraphs of cubic triangle-free planar graphs
- On a Turán type problem of Erdős
- On complete subgraphs of r-chromatic graphs
- Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
- The line index and minimum cut of weighted graphs
- On cycle lengths in graphs of moderate degree
- Two extremal problems in graph theory
- The size of the largest bipartite subgraphs
- Graph-theoretical methods in general function theory
- Upper bounds for \(f\)-domination number of graphs
- On the Turán density of \(\{1, 3\}\)-hypergraphs
- Extremal problems on components and loops in graphs
- Covers in hypergraphs
- Cycles of even length in graphs
- An extremal problem on degree sequences of graphs
- Dense induced bipartite subgraphs in triangle-free graphs
- The multicolor size-Ramsey numbers of cycles
- A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor
- Nearly-linear monotone paths in edge-ordered graphs
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- Eigenvector-based identification of bipartite subgraphs
- extremal aspects of the Erdős-Gallai-Tuza conjecture
- A note on bipartite subgraphs and triangle-independent sets
- On sufficient conditions for rainbow cycles in edge-colored graphs
- On the anti-Kekulé number and odd cycle transversal of regular graphs
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- On a valence problem in extremal graph theory
- On the chromatic number of Steiner triple systems of order 25
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Computing the largest bond and the maximum connected cut of a graph
- The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties
- Extremal metrics on graphs. I
- The bipartite edge frustration of hierarchical product of graphs
- On extremal graphs with bounded girth
- On a Conjecture of Erdős, Gallai, and Tuza
- Selected Topics in the Extremal Graph Theory
- Study of the bipartite edge frustration of graphs
- On an extremal inverse problem in graph theory
- scientific article; zbMATH DE number 3845613 (Why is no real title available?)
- Multiple domination
- An extremal problem onKr-free graphs
- Ramsey Size Linear Graphs
- On f-domination number of a graph
- scientific article; zbMATH DE number 1943959 (Why is no real title available?)
- A note on extremal results on directed acyclic graphs
- Problems and results on judicious partitions
- scientific article; zbMATH DE number 889960 (Why is no real title available?)
- scientific article; zbMATH DE number 6172670 (Why is no real title available?)
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Large triangle packings and Tuza's conjecture in sparse random graphs
- Local computation algorithms for spanners
- Beyond-planarity: Turán-type results for non-planar bipartite graphs
- Closing the random graph gap in Tuza's conjecture through the online triangle packing process
- scientific article; zbMATH DE number 975404 (Why is no real title available?)
- scientific article; zbMATH DE number 3298603 (Why is no real title available?)
- An extremal problem in graph theory
- scientific article; zbMATH DE number 3333193 (Why is no real title available?)
- Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
- A Spectral Erdős-Sós Theorem
- The bipartite edge frustration of composite graphs
- On bipartite restrictions of binary matroids
- On the complexity of some problems related to graph extensions
- The bipartite edge frustration of graphs under subdivided edges and their related sums
- Extremal properties of the bipartite vertex frustration of graphs
- Coloring a graph optimally with two colors
- An extension of a fixed point problem for simple graphs
- An FPT algorithm for splitting a necklace among two thieves
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- An FPT algorithm for splitting a necklace among two thieves
- New recursive constructions of amoebas and their balancing number
- Approximation algorithm and mechanism design for bisubmodular welfare maximization problem
- Structural properties of graph products
- Some remarks on Hajós' conjecture
- Graph spanners for group Steiner distances
- Bicriteria approximation for minimum dilation graph augmentation
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- A spectral Turán problem for a fixed tree
- On the integrality of an extreme solution to pluperfect graph and balanced systems
- How to make a graph bipartite
- The anti-Kekulé number of graphs
- The bipartite edge frustration of extension of splice and link graphs
This page was built for publication: On some extremal problems in graph theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396159)
