Doubt in a graph theory paper of Lovasz

Question

I am reading from the paper "Product Dimension of Graphs" by Lovasz, Nesetril and Pultr (available here). I have a doubt in the proof of Lemma 4.2 which establishes that for a graphs $G$ with order $n\ge 5$ and $\Delta(G^c)=n-2$ the product dimension is at most $n-2$.

The authors start by letting $H=G^c$. They let $a$ be the vertex of degree $\Delta (G^c)$ in $G^c$. Now $a$ is not adjacent to all other vertices in $G^c$ for then $\Delta(G^c)$ would have been $n-1$, which is against the hypothesis. So, there exists exactly one vertex $b$ such that $ab$ is not an edge in $G^c$.

Now I believe at this point there is a typographical error. The authors state:

Denote by $H'$ resp. $H^*$ the subgraphs of $H$ spanned by $V(H)\setminus \{a,b\}$.

I believe this should be:

Let $H'$ be the subgraph of $G^c$ induced by all the vertices except $a$. Also let $H^*$ be the subgraph of $G^c$ induced by all the vertices except $a$ and $b$.

Next they consider three cases:

Case A: $H^*$ has no edges.

Case B: $H^*$ has edges and the largest degree vertex of $H^*$ has degree at most $n-3$.

Case C: $H^*$ has edges and the largest degree vertex of $H^*$ has degree equal to $n-2$.

In Case A, the authors state that "obviously $\dim G\le n-2$". I do not understand this. Can someone explain?

Answer 1

I agree with your interpretation that $H'$ is the subgraph of $H$ induced by $V(H) \setminus \{a\}$ and $H^*$ is the subgraph of $H$ induced by $V(H) \setminus \{a,b\}$. In support of this, note that the three cases are stated as

• $H^*$ is discrete (has no edges),
• $H^*$ is not discrete and $\Delta(H') \le n-3$,
• $H^*$ is not discrete and $\Delta(H') = n-2$.

The third case is only possible if $H'$ has at least $n-1$ vertices, and in the third case, it is concluded that $d_H(b) = n-2$, which only follows if $H'$ includes the vertex $b$.

(The argument there is that in $H'$, no vertex other than $b$ can have degree $n-2$, because then it has degree $n-1$ in $H$, being also adjacent to $a$. But $\Delta(H) = n-2$. Therefore, if $\Delta(H') = n-2$, then it must be $b$ that has degree $n-2$ in $H'$, and since $ab \notin E(H)$, $b$ has degree $n-2$ in $H$ as well.)

---

Now on to your main question. In the first case, where $H^*$ has no edges, we know that $H = G^c$ has the following structure:

• Vertices $a$, $b$, and $v_1, \dots, v_{n-2}$.
• Edges $av_1, \dots, av_{n-2}$ and $bv_1, \dots, bv_k$ for some $0 \le k \le n-2$.

This is triangle-free, so by Proposition 2.3 in the paper, the dimension of $G$ is determined entirely by the edge chromatic number of $H$. If $\chi'(H) \le 1$, then $\dim G = \chi'(H) + 1$, and if $\chi'(H) \ge 2$, then $\dim G = \chi'(H)$.

To edge-color $H$, we must begin by coloring $av_1, \dots, av_{n-2}$ using $n-2$ distinct colors (since they all share the endpoint $a$). We can avoid using any more colors by coloring $bv_i$ the same color as $av_{i+1}$ (and, if we get all the way up to $bv_{n-2}$, coloring it the same color as $av_1$). Therefore $\chi'(H) = n-2$, and we conclude $\dim G = n-2$. (The lemma assumes $n \ge 5$, so in particular $\chi'(H) \ge 2$.)

I don't know if this is supposed to count as obvious, or if it's the intended argument, but at least it resolves the issue.

Answer 2

The graph dimension, $\dim(G)$, is defined as the smallest dimension in which the graph has a unit-distance representation. If $H^*$ has no edges, then $G^c$ has only edges connecting vertices to $a$ or $b$ or both. So, in $\mathbb{R}^3$, place $a$ and $b$ at $(\pm 1/2, 0, 0)$, and all the other nodes anywhere on the circle $(0, \frac{\sqrt{3}}{2}\sin\theta, \frac{\sqrt{3}}{2}\cos\theta)$. Then you have a unit-distance representation of $G^c$ in $\mathbb{R}^3$, showing that $\dim(G) \le 3 \le n-2$.

---

Edit: I'm leaving the above answer; but as pointed out in the comment, the definition of $\dim$ in the referenced paper is somewhat different. In the paper, the graph dimension $\dim(G)$ is the least $n$ such that $G$ can be embedded into ${\bf N}^n$, where ${\bf N}$ is the complete graph with natural numbers as vertices. Again note that if $H^*$ has no edges, then $G^c$ has only edges connecting vertices to $a$ or $b$ or both. Put $a$ at $(1,1,1)$. If $a$ and $b$ are connected, put $b$ at $(2,2,2)$; otherwise put $b$ at $(1,2,2)$. (That is, the first coordinate is used to decide if $a$ and $b$ are connected.) Finally, put each $c\not\in\{a, b\}$ at $(m_c,a_c,b_c)$, where $m_c=3,4,5,\ldots$ (different for each $c$), and $a_c=1$ or $2$ or $3$ if $c$ is connected to just $b$, just $a$, or both, and $b_c=1$ or $2$ or $3$ if $c$ is connected to just $a$, just $b$, or both. As this is an embedding of $G^c$ in ${\bf N}^3$, we have $\dim(G)\le 3 \le n-2$.