Cycle-connected graphs (Q1201258): Difference between revisions

A graph \(G\) is called \(K\)-connected, \(K\) a fixed collection of graphs, if every pair of edges of \(G\) is contained in a subgraph \(S\) of \(G\), where \(S\in K\). The authors discuss \(C_4\)-connected graphs, where \(C_4\) is a cycle of length four and compute the constant \(c''\) such that there exists a graph with \(cn^2\) edges \((n = |V(G)|)\) in which the largest \(C_4\)-connected subgraph has size at most \(c''\).