Diagrammfarbe minimiert die Anzahl der Farben in jedem unabhängigen Satz

Ist die folgende Behauptung bekannt?

Behauptung : Für jeden Graphen mit n Eckpunkten existiert eine Färbung von G, so dass jede unabhängige Menge mit höchstens O ( √) gefärbt ist$G$$n$$G$Farben.$O(\sqrt{n})$

Die folgende Behauptung ist mir bekannt, zählt aber möglicherweise nicht, weil sie unveröffentlicht ist: Jeder Graph auf Eckpunkten kann so gefärbt werden, dass jeder induzierte Teilgraph H der chromatischen Zahl höchstens k höchstens χ ( H ) + B- Farben verwendet, wobei B. ( B + 1 ) ≤ 2 k n .$n$$H$$k$$\chi(H)+B$$B(B+1)\leq 2kn$

Dies ist ein Beweis durch Induktion; Die Motivation bestand darin, Färbungen zu berücksichtigen, die nicht nur in der Grafik, sondern auch in allen induzierten Teilgraphen nur wenige Farben verwenden. Mir sind jedoch keine veröffentlichten Ergebnisse bekannt.

Nicht ganz das, wonach Sie fragen, aber hier ist eine Untergrenze - ein Diagramm, für das jede Färbung zu einem unabhängigen Satz führt, der mit gefärbt ist$\sqrt{n}$

$\sqrt{n}$$K_{\sqrt{n}}$$s$

$\sqrt{n}$$K$$K_{\sqrt{n}}$

Diese Untergrenze kann leicht auf verbessert werden$\sqrt{2n}$$K_1,K_2,..$$\Omega(\sqrt{n})$

$\alpha(G) \leq \sqrt{n}$$I$$G$$\alpha$$I$$G - I$$2,...,c$$K$$G$$K' = K - I$$K'$$\sqrt{n-\alpha}$$K$$1+\sqrt{n-\alpha} \leq \sqrt{n}$$\alpha \geq \sqrt{n}$