The Imperfection Ratio

A demand vector for a graph $G$ with node set $V$ is a non-negative vector of integers indexed by nodes of $G$. Given a graph $G$ and a demand vector $x=(x_v \; : \; v \in V(G))$ a coloring of the pair $(G.x)$ is an assignment of a set of $x_v$ colors to each node $v$ of $G$ such that two adjacet nodes receive disjoint sets of colors. Coloring the pair $(G,x)$ corresponds exactly to usual proper coloring of the replicated graph $G_x$. Let $G$ be a graph.Define the imperfection ratio of $G$ by setting

$$imp(G)=max_x \{ \frac{\chi_f(G_x)} { \omega(G_x)} \}$$

where the maximum is over all non-zero integral demand vectors $x$ and $\chi_F (G_x)$ and $\omega (G_x)$ are the fractional chromatic number and the clique number of the replicated graph $G_x$ respectively. (The ratios on the right-hand side above do indeed attain a maximum value). Observe that $imp(G) \geq 1$.

The next result establishes the connection of the imperfection ratio with perfection.

Proposition For any graph $G$, $imp(G)=1$ iff $G$ is perfect.

One of the motivations for studying graph imperfection is its connection to frequency assignment. With this motivation in mind one is particularly interested in bounding the imperfection ratio for graphs of relevant graph classes. One relevant graph class are for example unit disk graph, that is graphs the node set of which can be represented by unit size disks such that two nodes are adjacent if and only if the corresponding disks intersect. It is known that $imp(G)\leq 2.155$ for any unit disk graph $G$, and that there exists a unit disk graph $G$ with $imp(G)$ arbitrarily close to 3/2.

Conjecture: For any unit disk graph $G$, $imp(G)\leq 3/2$.

A subclass of unit disk graphs are the induced subgraphs of the triangular lattice. These graphs are of importance for channel assignment, since a pattern of omni-directional transmitters in two dimensions laid out like nodes of the triangular lattice in the plane give good coverage.

Let us now consider an induced subgraph $G$ of the triangular lattice $T$. Such a graph has a natural $3$-coloring. It is possible to have $\omega(G_x)=3$ and $\chi(G_x)$=4 for such a graph $G$. There is a polynomial-time coloring algorithm (by McDiarmid and Reed) which shows that for such a graph $G$ we always have

$$\chi(G_x) \leq \frac{4 \omega(G_x)+1}{3}$$

Thus $imp(G) \leq {4 \over 3}$ for any finite induced subgraph $G$ of the triangular lattice $T$. The $9$-cycle $C_9$ is an induced subgraph of the triangular lattice $T$. For any integer $k$ the graph obtained from $C_9$ by replicating each of its nodes $k$ times has clique number $2k$ and chromatic number $\lceil {9k\over 4} \rceil$ Is the ratio $9 \over 8$ of chromatic number to clique number asymptotically the worst (greatest) possible with large demands? This questions may be rephrased in terms of $imp(G)$ as follows:

Conjecture For any induced subgraph $G$ of the triangular lattice $T$, we have $imp(G) \leq {9\over 8}$

This would imply the following weaker and perhaps more tractable conjecture:

Conjecture If $G$ is a trianlgle-free induced subgraph of the triangular lattice then $\vert V(G)\vert \leq {9 \over 4} \alpha (G)$ (where $\alpha(G)$ is the size of the maximum stable set in $G$), and indeed $\chi_f(G) \leq {9 \over 4}$

To get a feeling for the behavior of the imperfection ratio, we mention the following elementary decomposition result: if $G$ is composed of two parts $G_1$ and $G_2$ that are either disjoint or overlap in a clique, then

$$imp(G)=max \{imp(G_1),imp(G_2) \}$$

The following is another property of imperfection which is desirable for any graph invariant related to perfection:

Proposition For any graph $G$ $imp(G)=imp(G^c)$ where $G^c$ denotes the completemt of $G$.

Another graph class of interest are planar graphs. It follows from the $4$-colour theorem that $imp(G)\leq 2$ for any planar graph $G$. It is known that one can improve a little on this but we conjecture that the true value is $3/2.$

Conjecture: For any planar graph $G$, $imp(G)\leq 3/2$.

Another area of interest are complexity issues concerning imperfection. It is known that it is NP hard to determine the imperfection ratio. One open question is whether for a fixed $k$ one can determine in polynomial time whether a graph $G$ satisfies $imp(G)\leq k$. For the special case of $k=1$, this is the recognition problem for perfect graphs. Another open question is how hard is it to approximate the imperfection ratio of a graph.

Initial contribution by Bruce Reed, extended by Stefanie Gerke

Back to the main index for Perfect Graphs.