Triangle-free induced subgraphs of polarity graphs

arXiv1703.06347MaRDI QIDQ6284492FDOQ6284492

Authors: Jared Loucks, Craig Timmons 

Publication date: 18 March 2017

Abstract: Given a finite projective plane $Pi$ and a polarity $heta$ of $Pi$, the corresponding polarity graph is the graph whose vertices are the points of $Pi$. Two distinct vertices $p$ and $p^{\prime }$ are adjacent if $p$ is incident to $heta(p^{\prime })$. Polarity graphs have been used in a variety of extremal problems, perhaps the most well-known being the Tur'{a}n number of the cycle of length four. We investigate the problem of finding the maximum number of vertices in an induced triangle-free subgraph of a polarity graph. Mubayi and Williford showed that when $Pi$ is the projective geometry $PG(2,q)$ and $heta$ is the orthogonal polarity, an induced triangle-free subgraph has at most $frac12q^2+O(q^{3/2})$ vertices. We generalize this result to all polarity graphs, and provide some interesting computational results that are relevant to an unresolved conjecture of Mubayi and Williford.

This page was built for publication: Triangle-free induced subgraphs of polarity graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284492)