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$ Commented 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
    Commented Mar 27, 2014 at 9:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .