Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
Copyright policy )Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
AbstractFor a bipartite graph , let be the largest such that either contains , a complete bipartite subgraph with parts of size , or the bipartite complement of contains as a subgraph. For a class of graphs , let . We say that a bipartite graph is strongly acyclic if neither nor its bipartite complement contains a cycle. By we denote the set of bipartite graphs with parts of size , which do not contain as an induced bipartite subgraph respecting the sides. One can easily show that for a positive if is not strongly acyclic. Here we ask whether is linear in for any strongly acyclic graph . We answer this question in the positive for all but four strongly acyclic graphs. We do not address this question for the remaining four graphs in this paper.
ddc:510, Erdős-Hajnal conjecture, homogeneous sets, bipartite, 510, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), forbidden induced subgraphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Mathematics, info:eu-repo/classification/ddc/510
ddc:510, Erdős-Hajnal conjecture, homogeneous sets, bipartite, 510, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), forbidden induced subgraphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, Mathematics, info:eu-repo/classification/ddc/510
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!