Chromatic Gallai identities operating on Lovsz number
If \(G\) is a triangle-free graph, then two Gallai identities can be written as \(\alpha (G)+\overline{\chi }(L(G))=|V(G)|=\alpha (L(G))+\overline{\chi }(G)\), where \(\alpha \) and \(\overline{\chi }\) denote the stability number and the clique-partition number, and \(L(G)\) is the line graph of\(G\). We show that, surprisingly, both equalities can be preserved for any graph \(G\) by deleting the edges of the line graph corresponding to simplicial pairs of adjacent arcs, according to any acyclic orientation of\(G\). As a consequence, one obtains an operator \(\Phi \) which associates to any graph parameter \(\beta \) such that \(\alpha (G) \le \beta (G) \le \overline{\chi }(G)\) forall graph \(G\), a graph parameter \(\Phi _\beta \) such that \(\alpha (G) \le \Phi _\beta (G) \le \overline{\chi }(G)\) forall graph \(G\). We prove that \(\vartheta (G) \le \Phi _\vartheta (G)\) and that \(\Phi _{\overline{\chi }_f}(G)\le \overline{\chi }_f(G)\) forall graph\(G\), where \(\vartheta \) is Lovsz theta function and \(\overline{\chi }_f\) is the fractional clique-partition number. Moreover, \(\overline{\chi }_f(G) \le \Phi _\vartheta (G)\) for triangle-free \(G\). Comparing to the previous strengthenings \(\Psi _\vartheta \) and \(\vartheta ^{+ \triangle }\) of \(\vartheta \), numerical experiments show that \(\Phi _\vartheta \) is a significant better lower bound for \(\overline{\chi }\) than \(\vartheta \).
gallai identities lovsz number graph coloring fractional chromatic number semidefinite programming 05c15 05c69 90c05 90c22 90c27