In the classic Maximum Weight Independent Set problem we are given a graph G with nonnegative weight function on vertices, and goal is to find an independent set in of maximum possible weight. While NP-hard general, give polynomial-time algorithm working any P6-free graph, that is, has no path 6 vertices as induced subgraph. This improves P5-free graphs Lokshtanov et al. [11], quasipolynomial-time [12]. The main technical contribution leading our result enumeration polynomial-size family F...

In the classic Maximum Weight Independent Set problem, we are given a graph G with nonnegative weight function on its vertices, and goal is to find an independent set in of maximum possible weight. While problem NP-hard general, give polynomial-time algorithm working any P 6 -free graph, that is, has no path vertices as induced subgraph. This improves 5 graphs Lokshtanov et al. [ 15 ] quasipolynomial-time 14 ]. The main technical contribution leading our result enumeration polynomial-size...

ABSTRACT One of the most fundamental results in graph theory is Mantel's theorem which determines maximum number edges a triangle‐free order . Recently, colorful variant this problem has been solved. In we consider graphs on common vertex set, think each as distinct color, and want to determine smallest color guarantees existence rainbow triangle. Here, solve analogous for directed without triangles, either or transitive, any colors. The constructions proofs essentially differ type forbidden...

.In 1959, Erdős and Gallai proved the asymptotically optimal bound for maximum number of edges in graphs not containing a path fixed length. Here, we study rainbow version their theorem, which one considers \(k \geq 1\) on common set vertices creating having from different asks each graph. We prove case three any 1\).Keywordsextremal graph theoryrainbow coloringTurán-type problemsMSC codes05C35

Abstract Let denote the maximum number of copies possible in an ‐vertex planar graph. The function has been determined when is a cycle length 3 or 4 by Hakimi and Schmeichel complete bipartite graph with smaller part size 1 2 Alon Caro. We determine exactly case path 3.

Abstract A graph $H$ is common if the number of monochromatic copies in a 2-edge-colouring complete $K_n$ asymptotically minimised by random colouring. Burr and Rosta, extending famous conjecture Erdős, conjectured that every common. The conjectures Erdős Rosta were disproved Thomason Sidorenko, respectively, late 1980s. Collecting new examples graphs had not seen much progress since then, although very recently few more verified to be flag algebra method or recent on Sidorenko’s conjecture....

In 1959 Erd\H os and Gallai proved the asymptotically optimal bound for maximum number of edges in graphs not containing a path fixed length. We investigate rainbow version theorem, which one considers $k \geq 1$ on common set vertices creating having from different asks each graph. prove case three any 1$.

In a rainbow version of the classical Turán problem one considers multiple graphs on common vertex set, thinking each graph as edges in distinct color, and wants to determine minimum number color which guarantees existence copy (having at most edge from graph) given graph. Here, we prove an optimal solution for this any directed star colors.

A conjecture of Erdős from 1967 asserts that any graph on n vertices which does not contain a fixed r-degenerate bipartite F has at most Cn2−1/r edges, where C is constant depending only F. We show this bound holds for large family graphs, including all blow-ups trees. Our results generalise many previously proven cases the conjecture, related Füredi and Alon, Krivelevich Sudakov. proof uses supersaturation random walk an auxiliary graph.

In this paper we disprove a conjecture of Lidický and Murphy about the number copies given graph in $K_r$-free give an alternative general conjecture. We also prove asymptotically tight bound on any bipartite radius at most~$2$ triangle-free graph.

We study the uniqueness of optimal solutions to extremal graph theory problems. Lovasz conjectured that every finite feasible set subgraph density constraints can be extended further by a so resulting is satisfied an asymptotically unique graph. This statement often referred as saying `every problem has finitely forcible optimum'. present counterexample conjecture. Our techniques also extend more general setting involving other types constraints.

Abstract We prove that for each odd integer , every graph on vertices without cycles of length less than contains at most . This extends the previous results maximum number pentagons in triangle‐free graphs, conjectured by Erdős 1984, and asymptotically determines generalized Turán In contrary to pentagon case, our proof is not computer‐assisted.

The Caccetta-Häggkvist Conjecture asserts that every oriented graph on $n$ vertices without directed cycles of length less than or equal to $l$ has minimum outdegree at most $(n-1)/l$. In this paper we state a conjecture for graphs missing transitive tournament $2^k+1$ vertices, with weaker assumption outdegree. We prove the follows from presented and show matching constructions all $k$ $l$. main advantage considering generalized is it reduces set extremal allows using an induction.We also...

Alon and F\"{u}redi (1993) showed that the number of hyperplanes required to cover $\{0,1\}^n\setminus \{0\}$ without covering $0$ is $n$. We initiate study such exact hyperplane covers hypercube for other subsets hypercube. In particular, we provide solutions $\{0,1\}^n$ while missing up four points give asymptotic bounds in general case. Several interesting questions are left open.

Let d_i(G) be the density of 3-vertex i-edge graph in a G, i.e., probability that three random vertices induce subgraph with i edges. S set all quadruples (d_0,d_1,d_2,d_3) are arbitrary close to densities large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined projection (d_0,d_3) plane. We determine remaining planes.