Return to Answer

The supremum of the quantity you are interested in, over the class of all finite graphs, is at least $\frac13$.

For the time being, I do neither know whether this supremum is larger than $\frac13$, nor whether the value $\frac13$ can be attained by any finite graph.

Here are some details.

It can be proved that there is a sequence of finite graphs on which the quantity converges to $\frac13$.

This sequence consists of triangle-free, three-colorable, Cayley graphs only: the sequence $\mathrm{And}_t$ of Andrásfai graphs (cf. e.g. the book of Godsil and Royle on algebraic graph theory).

Let $q_{\mathrm{absolute}}(G)$ denote the graph invariant (FiniteGraphs)$\longrightarrow$ $\mathbb{N}$ you defined.

Let $q(G) := q_{\mathrm{relative}}(G) := \frac{1}{\lvert G\rvert} q_{\mathrm{absolute}}(G)$ the quantity about which you asked how large it can get when $G$ ranges over all finite graphs.

It can be proved that the supremum of $q(G)$ over the class of all graphs is at least $\frac13$.

Since $\mathrm{And}_t$ is triangle-free, i.e., $\omega(\mathrm{And}_t)=2$, a transversal of the maximum cliques is equivalent to a cover of the edges by vertices (usually, and somewhat counterintuitively, called a vertex cover in contemporary graph theory texts).

So for any triangle-free graph $G$, the quantity $\min_T\lvert T\rvert$, in your sense, without the penalty-subtrahend, is just $\tau(G)$, the covering number of $G$.

This will now be used to give a rough lower bound on your quantity $q(G)$. The penality-subtrahend will just be estimated away, making use of the fact that Andrásfai graphs have relatively small independence number, using a bound in terms of the independence number (I decided not to think about how much the bound of $\frac13$ can be improved if one does not do this; this would require an analysis of the structure of the set of all independent sets of $\mathrm{And}_t$, which should be a straightforward task).

For every natural number $t$, the $t$-th Andrásfai graph $\mathrm{And}_t$ has

$\lvert \mathrm{And}_t\rvert = 3t-1$,

$\alpha(\mathrm{And}_t) = t = \tfrac13(\lvert \mathrm{And}_t\rvert+1)$,

$\tau(\mathrm{And}_t) = 2t-1 = \lvert \mathrm{And}_t\rvert - t$.

We can now argue as follows, abbreviating $n_t:=\lvert\mathrm{And}_t\rvert$,

$\sup_{\text{allfinitegraphs}} q(G)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(\min_T \min_{A\subseteq T} \lvert T\rvert - \lvert A\rvert)(\mathrm{And}_t)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \alpha( \mathrm{And}_t ) + (\min_T \lvert T\rvert )(\mathrm{And}_t) )$

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \tfrac13(n_t+1) + n_t - \frac13(n_t+1)) $

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}(\tfrac13 - \frac{2}{3n_t} )$

$=$

$\frac13$

the latter since arbitrarily large Andrásfai graphs exist.

The supremum $q$ of the quantity $q(G)$ you are interested in, over the class of all finite graphs, is at least $\frac13$.

For the time being, I do neither know whether $q$ is larger than $\frac13$, nor whether the value $\frac13$ can be attained by any finite graph.

Here are some details.

It can be proved that there is a sequence of finite graphs on which the quantity converges to $\frac13$.

This sequence consists of triangle-free, three-colorable, Cayley graphs only: the sequence $\mathrm{And}_t$ of Andrásfai graphs (cf. e.g. the book of Godsil and Royle on algebraic graph theory).

Let $q_{\mathrm{absolute}}(G)$ denote the graph invariant (FiniteGraphs)$\longrightarrow$ $\mathbb{N}$ you defined.

Let $q(G) := q_{\mathrm{relative}}(G) := \frac{1}{\lvert G\rvert} q_{\mathrm{absolute}}(G)$ the quantity about which you asked how large it can get when $G$ ranges over all finite graphs.

It can be proved that the supremum of $q(G)$ over the class of all graphs is at least $\frac13$.

Since $\mathrm{And}_t$ is triangle-free, i.e., $\omega(\mathrm{And}_t)=2$, a transversal of the maximum cliques is equivalent to a cover of the edges by vertices (usually, and somewhat counterintuitively, called a vertex cover in contemporary graph theory texts).

So for any triangle-free graph $G$, the quantity $\min_T\lvert T\rvert$, in your sense, without the penalty-subtrahend, is just $\tau(G)$, the covering number of $G$.

This will now be used to give a rough lower bound on your quantity $q(G)$. The penality-subtrahend will just be estimated away, making use of the fact that Andrásfai graphs have relatively small independence number, using a bound in terms of the independence number (I decided not to think about how much the bound of $\frac13$ can be improved if one does not do this; this would require an analysis of the structure of the set of all independent sets of $\mathrm{And}_t$, which should be a straightforward task).

For every natural number $t$, the $t$-th Andrásfai graph $\mathrm{And}_t$ has

$\lvert \mathrm{And}_t\rvert = 3t-1$,

$\alpha(\mathrm{And}_t) = t = \tfrac13(\lvert \mathrm{And}_t\rvert+1)$,

$\tau(\mathrm{And}_t) = 2t-1 = \lvert \mathrm{And}_t\rvert - t$.

We can now argue as follows, abbreviating $n_t:=\lvert\mathrm{And}_t\rvert$,

$q$ $=$ $\sup_{\text{allfinitegraphs}} q(G)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(\min_T \min_{A\subseteq T} \lvert T\rvert - \lvert A\rvert)(\mathrm{And}_t)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \alpha( \mathrm{And}_t ) + (\min_T \lvert T\rvert )(\mathrm{And}_t) )$

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \tfrac13(n_t+1) + n_t - \frac13(n_t+1)) $

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}(\tfrac13 - \frac{2}{3n_t} )$

$=$

$\frac13$

the latter since arbitrarily large Andrásfai graphs exist.

Now let us write, for any natural number $k$,

$$q_k := \sup_{\text{all finite graphs $G$ with $\omega(G)=k$}}q_{\mathrm{relative}}(G) $$

for the quantity you are more intersted in. A more important question than what value the single universal constant $q\in[\frac13,1]$ has, is to analyse the function

$$ S: \mathbb{N}\rightarrow [0,1] $$ $$ k\mapsto q_k$$.

It would be helpful for systematic reasons if others would use this notation.

The supremum of the quantity you are interested in, over the class of all finite graphs, is at least $\frac13$.

For the time being, I do neither know whether this supremum is larger than $\frac13$, nor whether the value $\frac13$ can be attained by any finite graph.

Here are some details.

It can be proved that there is a sequence of finite graphs on which the quantity converges to $\frac13$.

This sequence consists of triangle-free, three-colorable, Cayley graphs only: the sequence $\mathrm{And}_t$ of Andrásfai graphs (cf. e.g. the book of Godsil and Royle on algebraic graph theory).

Let $q_{\mathrm{absolute}}(G)$ denote the graph invariant (FiniteGraphs)$\longrightarrow$ $\mathbb{N}$ you defined.

Let $q(G) := q_{\mathrm{relative}}(G) := \frac{1}{\lvert G\rvert} q_{\mathrm{absolute}}(G)$ the quantity about which you asked how large it can get when $G$ ranges over all finite graphs.

It can be proved that the supremum of $q(G)$ over the class of all graphs is at least $\frac13$.

Since $\mathrm{And}_t$ is triangle-free, i.e., $\omega(\mathrm{And}_t)=2$, a transversal of the maximum cliques is equivalent to a cover of the edges by vertices (usually, and somewhat counterintuitively, called a vertex cover in contemporary graph theory texts).

So for any triangle-free graph $G$, the quantity $\min_T\lvert T\rvert$, in your sense, without the penalty-subtrahend, is just $\tau(G)$, the covering number of $G$.

This will now be used to give a rough lower bound on your quantity $q(G)$. The penality-subtrahend will just be estimated away, making use of the fact that Andrásfai graphs have relatively small independence number, using a bound in terms of the independence number (I decided not to think about how much the bound of $\frac13$ can be improved if one does not do this; this would require an analysis of the structure of the set of all independent sets of $\mathrm{And}_t$, which should be a straightforward task).

For every natural number $t$, the $t$-th Andrásfai graph $\mathrm{And}_t$ has

$\lvert \mathrm{And}_t\rvert = 3t-1$,

$\alpha(\mathrm{And}_t) = t = \tfrac13(\lvert \mathrm{And}_t\rvert+1)$,

$\tau(\mathrm{And}_t) = 2t-1 = \lvert \mathrm{And}_t\rvert - t$.

We can now argue as follows.

$\sup_{\text{allfinitegraphs}} q(G)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(\min_T \min_{A\subseteq T} \lvert T\rvert - \lvert A\rvert)(\mathrm{And}_t)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(- \alpha( \mathrm{And}_t ) + (\min_T \lvert T\rvert )(\mathrm{And}_t) )$

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(- \tfrac13(\lvert \mathrm{And}_t\rvert+1) + \lvert \mathrm{And}_t\rvert - \frac13(\lvert\mathrm{And}_t\rvert+1)) $

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}(\tfrac13 - \frac{2}{3\lvert\mathrm{And}_t\rvert} )$

$=$

$\frac13$

the latter since arbitrarily large Andrásfai graphs exist.

The supremum of the quantity you are interested in, over the class of all finite graphs, is at least $\frac13$.

For the time being, I do neither know whether this supremum is larger than $\frac13$, nor whether the value $\frac13$ can be attained by any finite graph.

Here are some details.

It can be proved that there is a sequence of finite graphs on which the quantity converges to $\frac13$.

This sequence consists of triangle-free, three-colorable, Cayley graphs only: the sequence $\mathrm{And}_t$ of Andrásfai graphs (cf. e.g. the book of Godsil and Royle on algebraic graph theory).

Let $q_{\mathrm{absolute}}(G)$ denote the graph invariant (FiniteGraphs)$\longrightarrow$ $\mathbb{N}$ you defined.

Let $q(G) := q_{\mathrm{relative}}(G) := \frac{1}{\lvert G\rvert} q_{\mathrm{absolute}}(G)$ the quantity about which you asked how large it can get when $G$ ranges over all finite graphs.

It can be proved that the supremum of $q(G)$ over the class of all graphs is at least $\frac13$.

Since $\mathrm{And}_t$ is triangle-free, i.e., $\omega(\mathrm{And}_t)=2$, a transversal of the maximum cliques is equivalent to a cover of the edges by vertices (usually, and somewhat counterintuitively, called a vertex cover in contemporary graph theory texts).

So for any triangle-free graph $G$, the quantity $\min_T\lvert T\rvert$, in your sense, without the penalty-subtrahend, is just $\tau(G)$, the covering number of $G$.

This will now be used to give a rough lower bound on your quantity $q(G)$. The penality-subtrahend will just be estimated away, making use of the fact that Andrásfai graphs have relatively small independence number, using a bound in terms of the independence number (I decided not to think about how much the bound of $\frac13$ can be improved if one does not do this; this would require an analysis of the structure of the set of all independent sets of $\mathrm{And}_t$, which should be a straightforward task).

For every natural number $t$, the $t$-th Andrásfai graph $\mathrm{And}_t$ has

$\lvert \mathrm{And}_t\rvert = 3t-1$,

$\alpha(\mathrm{And}_t) = t = \tfrac13(\lvert \mathrm{And}_t\rvert+1)$,

$\tau(\mathrm{And}_t) = 2t-1 = \lvert \mathrm{And}_t\rvert - t$.

We can now argue as follows, abbreviating $n_t:=\lvert\mathrm{And}_t\rvert$,

$\sup_{\text{allfinitegraphs}} q(G)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(\min_T \min_{A\subseteq T} \lvert T\rvert - \lvert A\rvert)(\mathrm{And}_t)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \alpha( \mathrm{And}_t ) + (\min_T \lvert T\rvert )(\mathrm{And}_t) )$

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{n_t}(- \tfrac13(n_t+1) + n_t - \frac13(n_t+1)) $

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}(\tfrac13 - \frac{2}{3n_t} )$

$=$

$\frac13$

the latter since arbitrarily large Andrásfai graphs exist.

The supremum of the quantity you are interested in, over the class of all finite graphs, is at least $\frac13$.

For the time being, I do neither know whether this supremum is larger than $\frac13$, nor whether the value $\frac13$ can be attained by any finite graph.

Here are some details.

It can be proved that there is a sequence of finite graphs on which the quantity converges to $\frac13$.

This sequence consists of triangle-free, three-colorable, Cayley graphs only: the sequence $\mathrm{And}_t$ of Andrásfai graphs (cf. e.g. the monograph of Godsil and Royle on algebraic graph theory).

Let $q_{\mathrm{absolute}}(G)$ denote the function (FiniteGraphs)$\mapsto$ $\mathbb{N}$ you defined.

Let $q(G) := q_{\mathrm{relative}}(G) := \frac{1}{\lvert G\rvert} q_{\mathrm{absolute}}(G)$ the quantity about which you asked how large it can get when $G$ ranges over all finite graphs.

It can be proved that the supremum of $q(G)$ over the class of all graphs is at least $\frac13$.

Since $\mathrm{And}_t$ is triangle-free, i.e., $\omega(\mathrm{And}_t)=2$, a transversal of the maximum cliques is equivalent to a cover of the edges by vertices (usually, and somewhat counterintuitively, called a vertex cover in contemporary graph theory texts).

So for any triangle-free graph $G$, the quantity $\min_T\lvert T\rvert$, in your sense, without the penalty-subtrahend, is just $\tau(G)$, the covering number of $G$.

This will now be used to give a rough lower bound on your quantity $q(G)$. The penality-subtrahend will just be estimated away, making use of the fact that Andrásfai graphs have relatively small independence number, using a bound in terms of the independence number (I decided not to think about how much the bound of $\frac13$ can be improved if one does not do this; this would require an analysis of the structure of the set of all independent sets of $\mathrm{And}_t$, which should be a straightforward task).

For every natural number $t$, the $t$-th Andrásfai graph $\mathrm{And}_t$ has

$\lvert \mathrm{And}_t\rvert = 3t-1$,

$\alpha(\mathrm{And}_t) = t = \tfrac13(\lvert \mathrm{And}_t\rvert+1)$,

$\tau(\mathrm{And}_t) = 2t-1 = \lvert \mathrm{And}_t\rvert - t$.

We can now argue as follows.

$\sup_{\text{allfinitegraphs}} q(G)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(\min_T \min_{A\subseteq T} \lvert T\rvert - \lvert A\rvert)(\mathrm{And}_t)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(- \alpha( \mathrm{And}_t ) + (\min_T \lvert T\rvert )(\mathrm{And}_t) )$

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(- \tfrac13(\lvert \mathrm{And}_t\rvert+1) + \lvert \mathrm{And}_t\rvert - \frac13(\lvert\mathrm{And}_t\rvert+1)) $

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}(\tfrac13 - \frac{2}{3\lvert\mathrm{And}_t\rvert} )$

$=$

$\frac13$

the latter since arbitrarily large Andrásfai graphs exist.

The supremum of the quantity you are interested in, over the class of all finite graphs, is at least $\frac13$.

For the time being, I do neither know whether this supremum is larger than $\frac13$, nor whether the value $\frac13$ can be attained by any finite graph.

Here are some details.

It can be proved that there is a sequence of finite graphs on which the quantity converges to $\frac13$.

This sequence consists of triangle-free, three-colorable, Cayley graphs only: the sequence $\mathrm{And}_t$ of Andrásfai graphs (cf. e.g. the book of Godsil and Royle on algebraic graph theory).

Let $q_{\mathrm{absolute}}(G)$ denote the graph invariant (FiniteGraphs)$\longrightarrow$ $\mathbb{N}$ you defined.

Let $q(G) := q_{\mathrm{relative}}(G) := \frac{1}{\lvert G\rvert} q_{\mathrm{absolute}}(G)$ the quantity about which you asked how large it can get when $G$ ranges over all finite graphs.

It can be proved that the supremum of $q(G)$ over the class of all graphs is at least $\frac13$.

Since $\mathrm{And}_t$ is triangle-free, i.e., $\omega(\mathrm{And}_t)=2$, a transversal of the maximum cliques is equivalent to a cover of the edges by vertices (usually, and somewhat counterintuitively, called a vertex cover in contemporary graph theory texts).

So for any triangle-free graph $G$, the quantity $\min_T\lvert T\rvert$, in your sense, without the penalty-subtrahend, is just $\tau(G)$, the covering number of $G$.

This will now be used to give a rough lower bound on your quantity $q(G)$. The penality-subtrahend will just be estimated away, making use of the fact that Andrásfai graphs have relatively small independence number, using a bound in terms of the independence number (I decided not to think about how much the bound of $\frac13$ can be improved if one does not do this; this would require an analysis of the structure of the set of all independent sets of $\mathrm{And}_t$, which should be a straightforward task).

For every natural number $t$, the $t$-th Andrásfai graph $\mathrm{And}_t$ has

$\lvert \mathrm{And}_t\rvert = 3t-1$,

$\alpha(\mathrm{And}_t) = t = \tfrac13(\lvert \mathrm{And}_t\rvert+1)$,

$\tau(\mathrm{And}_t) = 2t-1 = \lvert \mathrm{And}_t\rvert - t$.

We can now argue as follows.

$\sup_{\text{allfinitegraphs}} q(G)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(\min_T \min_{A\subseteq T} \lvert T\rvert - \lvert A\rvert)(\mathrm{And}_t)$

$\geq$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(- \alpha( \mathrm{And}_t ) + (\min_T \lvert T\rvert )(\mathrm{And}_t) )$

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}\frac{1}{\lvert\mathrm{And}_t\rvert}(- \tfrac13(\lvert \mathrm{And}_t\rvert+1) + \lvert \mathrm{And}_t\rvert - \frac13(\lvert\mathrm{And}_t\rvert+1)) $

$=$

$\sup_{t\in\mathbb{Z}_{\geq 2}}(\tfrac13 - \frac{2}{3\lvert\mathrm{And}_t\rvert} )$

$=$

$\frac13$

the latter since arbitrarily large Andrásfai graphs exist.