2
$\begingroup$

Let $G$ be a tripartite graph with partite sets $A,B,C$. The graphs $A\cup B$, $B\cup C$ and $C\cup A$ are each bipartite. Let the maximum degree of the graph be $\Delta$.

Now, we know that the List edge coloring conjecture is true for bipartite graphs, that is, the edge choosability is same as edge chromatic number or chromatic index for bipartite graphs. Now, first we list-edge color the graph $A\cup B$, then list-edge color the graph $B\cup C$ and finally the remaining graph $C\cup A$. Then this should give a list coloring of the graph $G$ right. The lists while coloring the graphs $A\cup B$, $B\cup C$ and $C\cup A$ are are actually lists of length $\chi'(G)$, where $\chi'$ is the chromatic index. Where is the fault in this argument? Thanks beforehand.

Improve this question
$\endgroup$
4
  • $\begingroup$ This may not be a list coloring, as there may be repeated colors shared by a vertex while coloring $A \cup B$ and $B \cup C$. Further arguments are required to ensure that there are no repeated colors. $\endgroup$
    – LeechLattice
    Sep 5, 2019 at 23:13
  • $\begingroup$ @Bullet51 actually I am coloring the edges of the bipartite graphs. So, when I give a list of length $\chi'(G)$, I think I would have enough scope to avoid the intersection of two incident edges having same color; because the maximum degree of the bipartite graphs is always less than or equal to that of the whole graph and $\chi'(G)\ge\Delta(G)$. I think by colors shared by a vertex, you meant intersection of two incident edges having same color? $\endgroup$
    – vidyarthi
    Sep 6, 2019 at 6:29
  • 6
    $\begingroup$ I'm voting to close this question as off-topic because MO is not a site for checking proposed proofs. $\endgroup$
    – LSpice
    Sep 16, 2019 at 21:21
  • $\begingroup$ @LSpice Actually, I did not propose any proof, rather a heuristic, which, later was seen so to be false, by myself, as posted in an answer. Well, many questions in this site are actually of this form. Maybe, in this case, the problem was more celebrated. $\endgroup$
    – vidyarthi
    Sep 17, 2019 at 4:51

1 Answer 1

Reset to default
1
$\begingroup$

The procedure, as such, may not give a proper coloring for a given graph. Consider the graph having $4$ vertices, $1,2,3,4$ given by the adjacency list $1-4,2-4,1-3,2-3,3-4$. Here the vertices $1,2$ form a part $A$, and vertices $3$ and $4$ belong to different parts, say $B$ and $C$ respectively. We know that $3$ is the chromatic index. Let us assume we have the list of $a,b,c$ to begin with. Consider giving the same list of $a,b$ to color the edges $1-3$ and $2-3$. We give the list colors $b,c$ to the edges $1-4$ and $2-4$. Then, we are left with a situation that we cannot color the remaining edge $3-4$.

May be, an ordering of the bipartite graphs is needed. Specifically, in the above example, if we first color the edges of the bipartite graphs incident to the vertices having largest maximum degree first, that is , first color the edges of $A\cup B$ and then color the edges of $B\cup C$, and then, finally the edges of $A\cup C$, we could arrive at a proper coloring.

Improve this answer
$\endgroup$

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