\documentclass[11pt]{article} \pdftrailerid{} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{mathrsfs} \usepackage{microtype} \usepackage{enumitem} \usepackage{booktabs} \usepackage{tikz} \usetikzlibrary{arrows.meta,positioning} \usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref} \hypersetup{pdftitle={Hardness of finding large independent sets in three-colorable graphs},pdfauthor={OpenAI}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\T}{\mathbb T} \newcommand{\R}{\mathbb R} \newcommand{\Q}{\mathbb Q} \newcommand{\N}{\mathbb N} \newcommand{\E}{\mathbb E} \newcommand{\eps}{\varepsilon} \DeclareMathOperator{\dist}{dist} \DeclareMathOperator{\Lip}{Lip} \DeclareMathOperator{\val}{val} \DeclareMathOperator{\id}{id} \setlist{itemsep=3pt,topsep=5pt} \setlength{\emergencystretch}{2em} \title{Hardness of finding large independent sets\\in three-colorable graphs} \author{OpenAI} \date{September 24, 2026} \begin{document} \maketitle \begin{abstract} We prove that, for every fixed $0<\delta<1/3$, it is NP-hard to distinguish three-colorable graphs from graphs in which every independent set has fewer than $\delta$ times the number of vertices. Consequently, for every fixed integer $c\ge3$, finding a proper $c$-coloring of a three-colorable graph is NP-hard. \end{abstract} \input{sections/introduction} \input{sections/preliminaries} \input{sections/construction} \input{sections/lists} \input{sections/alignment} \input{sections/coefficient} \input{sections/parameters} \input{sections/alignment-proof} \bibliographystyle{plain} \bibliography{references} \end{document}