2
$\begingroup$

If any perfect graph $G$ has no $n+1$ clique then can one always find $n$ bipartite graphs $B_1,\ldots B_n$ such that $G=\cup_{k=1}^nB_k$?

$\endgroup$

1 Answer 1

2
$\begingroup$

Any $(n+1)$-colorable graph is the edge-disjoint union of $n$ bipartite graphs. Order the colors as $1, 2, \dots, n+1$ and let $B_k$ be the subgraph formed by all edges between color $k$ and colors $k+1, k+2, \dots, n+1$.

We can do better and use about $\log_2 n$ colors: if a graph is $2^k$-colorable, then name the colors after elements of $\{0,1\}^k$, and for $i=1, \dots, k$ let $B_i$ be the graph joining colors with a $0$ in the $i^{\text{th}}$ position to colors with a $1$ in the $i^{\text{th}}$ position.

(As stated, some edges will appear in multiple $B_i$, but if that's a problem we can make an arbitrary choice for each such edge.)

$\endgroup$
0

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.