In finite graph theory, there are many (in)equalities which relate the integer value of a certain graph invariant (e.g. domination or chromatic number) for the product of two finite graphs (e.g. tensor, Cartesian, strong product, etc.) to the value of the same invariant for each component.

Such (in)equalities are often formulated as $i(G*H)\sim f(i(G), i(H))$ where $i$ is the operator assigning a certain integer-valued invariant to the graph, $*$ is a particular type of graph product, $\sim$ is the (in)equality sign, and $f$ is a function from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$. For instance, see Vizing's conjecture.

However, such (in)equalities seem to be quite vulnerable to the finiteness condition and may fail so badly if one brings infinite graphs and transfinite-valued graph invariants into the play as a direct generalization of the original statement. A typical example is Hajnal's proof (cf. MR0815579) of the failure of Hedetniemi's conjecture for infinite graphs. (See also Assaf Rinot's result along these lines.)

Here in this post, I look for more results of this type, namely the instances of the failure of the (open/proved) (in)equalities of the described form in the infinite case. Of course, some of these conjectures might be wide open in their finite case, yet have some relatively easy counterexamples in the infinite form.

Question 1. What are examples of finite graph (in)equalities of the form $i(G*H)\sim f(i(G), i(H))$ which (may) fail for the infinite graphs (up to consistency)?

I am particularly interested in the case of Vizing's conjecture ($VC$):

Question 2. Can $VC$ fail for the infinite graphs?

Another line of thought might be considering a case where a statement fails in the finite case but holds for infinite graphs. Particularly, this might be the case for "Ramsey-type" graph invariants which require the underlying structures to be very large to behave nicely.

Question 3. What are examples of graph (in)equalities of the form $i(G*H)\sim f(i(G), i(H))$ which fail for the finite graphs but hold for certain class of infinite graphs?


1 Answer 1


Sorry for the confusion, I am being slow today.

Letting $\gamma(G)$ be the domination number of $G$, we have the trivial inequality $$\gamma(G\times H) \geq {\rm max}(\gamma(G),\gamma(H)).$$ This is because a dominating set for $G\times H$ will project onto a dominating set in either factor. So if either domination number is infinite then ${\rm max}(\gamma(G), \gamma(H)) = \gamma(G)\gamma(H)$ and Vizing's conjecture holds.

If both domination numbers are finite, but $G$ or $H$ is infinite, there could be a real question here. Domination number can strange for infinite graphs. E.g., I can give an infinite graph with domination number $k$ which is the union of an increasing sequence of finite graphs each of which has domination number $1$.

  • 1
    $\begingroup$ I am not finding either of the inequalities you state trivial. Could you offer a hint for those of us who have not had coffee yet today? I'm especially curious about the right hand side which is almost a negation of Vizing's conjecture. (Or are you assuming the left hand side is not finite to start?) Gerhard "Some Days Hints Are Needed" Paseman, 2018.07.14. $\endgroup$ Jul 14, 2018 at 15:34
  • $\begingroup$ @GerhardPaseman: You are quite right, my answer was foolish. $\endgroup$
    – Nik Weaver
    Jul 14, 2018 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.