Chromatic number of t-perfect graphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph and write $x(U)=\sum_{v\in U}x_v$. A stable set is a vertex set containing no edge, and $\operatorname{STAB}(G)$ is the convex hull of its characteristic vectors. Define the odd-cycle relaxation \[ \begin{split} Q(G)=\{x\in[0,1]^V:\;&x_u+x_v\le1\quad(uv\in E),\\ &x(V(C))\le (|V(C)|-1)/2\quad\text{for every odd simple cycle }C\}. \end{split} \] The graph is called $t$-perfect if $Q(G)=\operatorname{STAB}(G)$. The coordinate upper bounds make the definition apply also to isolated vertices, whose presence does not affect the colouring question.

Is every $t$-perfect graph properly colourable with at most four colours? Explicitly, does there always exist a function \[ f:V\longrightarrow\{1,2,3,4\},\qquad f(u)\ne f(v)\quad(uv\in E)? \] Equivalently, can $V$ be partitioned into at most four stable sets? No planarity, forbidden-claw, or triangle-free assumption is included. The number four is absolute and must not grow with the number of vertices. The defining polyhedral equality concerns fractional stable-set constraints; converting it into a bounded partition of all vertices is the additional requirement. A bound on the fractional chromatic number or a larger fixed colour bound does not by itself answer this four-colour conjecture.

Short English statement

Must every graph whose stable-set polytope is described by edge and odd-cycle inequalities admit a proper colouring with four colours?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000011 (AMR-029-0011), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Chromatic number of t-perfect graphs. Original source indexed by AMR-029-0011. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Chromatic number of t-perfect graphs. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Chromatic_number_of_t-perfect_graphs.