2
$\begingroup$

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?


Added

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 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$ Mar 26, 2014 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, 2014 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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