The inflation of graph $G$ is a graph $I(G)$ which is obtained by replacing each vertex $x$ by a complete graph $K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$.

Let $G$ be a connected cubic graph. $I(G)$ is line graph (and claw-free).

Experimental data on up to $14$ vertices suggests:

$$\chi'(G) = \chi'(I(G)) \qquad (1)$$

$I(G)$ is perfect (2)

Is (1) and/or (2) true?


EdgarTheWise's answer shows hamiltonian cycle and edge coloring is NP-complete for cubic perfect line graphs.


I believe that both (1) and (2) are true. Let us denote the vertices of $I(G)$ as follows: $V(I(G)) = \{ u^v : uv \in E(G) \}$, so that $E(I(G)) = \{ u^vv^u: uv \in E(G) \} \cup \{ u^vu^w: v\neq w; uv, uw \in E(G) \}$

As for (1), both $G$ and $I(G)$ are cubic, so by Vizing's theorem we have $\chi'(G), \chi'(I(G)) \in \{3, 4\}$.

If $\chi'(G) = 3$, then pick a 3-edge-colouring $c : E(G) \to \{1,2,3\}$. Let $c_I$ be defined as follows: $$c_I(u^vv^u) = c(uv),$$ $$c_I(u^vu^w) \in \{1,2,3\} \setminus \{ c(uv), c(uw)\},$$ where the second formula uniquely defines $c_I$, since $c(uv) \neq c(uw)$.

With this $c_I$, the edges incident to a vertex $u^v \in V(I(G))$ and their respective colours are: $u^vv^u, u^vu^w, u^vu^y$ and $c(uv), c(uy), c(uw)$, which are distinct (where the neighbours of $u$ are $\{v,w,y\}$). Therefore, $\chi'(I(G)) \le 3$.

For the other direction, if $\chi'(I(G)) = 3$, let $c_I : E(I(G)) \to \{1,2,3\}$ denote a valid 3-edge-colouring. Let $c: E(G) \to \{1,2,3\}$ be defined as $c(uv) = c_I(u^vv^u)$.

Assume $c(uv) = c(uw)$ for some vertex $u$ with neighbours $\{v,w,y\}$. This won't work out: if $k = c_I(u^vv^u) = c_I(u^ww^u)$, then each edge of the triangle $u^v, u^w, u^y$ should be given one of the two colours $\{1,2,3\} \setminus \{k\}$: impossible. Therefore, $c$ is a good 3-edge-colouring, so $\chi'(G) \le 3$.

As for (2), if you don't mind relying on a deep and difficult result, it's easy to verify the conditions of the Strong Perfect Graph Theorem:

In an induced cycle of length $>3$, at most 2 out of the 3 vertices $u^v, u^w, u^y$ may be present. It cannot happen that exactly 1 of these is present (degree would fall to 1). So for each $u \in V(G)$, we have 0 or 2 vertices in the cycle, an even number overall.

An "anti-hole" of length 5 is the same as a hole of length 5; for anti-holes of length $\ge 7$, we'd need to have vertices of degree $\ge 4$, which we don't.

  • 1
    $\begingroup$ you don't need to go all the way to the strong perfect graph theorem for (2). By Brook's theorem, I(G) is 3-colorable. To check perfectness, all tou need to show now is that any non-bipartite subgraph contains a triangle. So take a shortest odd cycle longer than 3 in your subgraph. By your argument, it has a chord, yielding a shorter odd cycle as a subgraph---either a triangle, or a contradiction that the cycle was shortest. $\endgroup$ – Flo Pfender Mar 26 '14 at 21:37
  • $\begingroup$ As a side effect this is another proof that edge coloring cubic perfect line graphs is NP-complete. $\endgroup$ – joro Mar 27 '14 at 9:34

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.