1
$\begingroup$

Consider an even order, balanced(both partitions have same vertices) bipartite regular graph of order greater than or equal to $12$ and degree atleast six and divisible by $6$. Then is the graph of Type 1(totally colorable by $\Delta+1$ colors where $\Delta$ is the maximum degree)?

By petersen theorem, the graph has 2-factor( in fact k-factors for $k\le2n$, where $2n$ be the total number of vertices). Again, it is a union of disjoint $1$ factors(perfect matchings).Could these be used to provide a total coloring?

Apart from this, since the degree is also divisible by $3$(i.e. divisible by $6$), then, we may be able to find cycles of order divisible by $3$($6$); and since cycles whose order is divisible by $3$ can be totally colored(each pair of adjacent or incident elements of graph receive different colors) with $3$ colors, therefore we can also totally color each disjoint cycle in the graph using just three colors. Can we use this fact to totally color the whole graph with ($\Delta+1$) colors?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ how the order of cycles is connected to the degrees? $\endgroup$
    – Fedor Petrov
    Jan 22, 2019 at 13:22
  • 1
    $\begingroup$ @FedorPetrov edited the question slightly. Please read now. $\endgroup$
    – vidyarthi
    Jan 22, 2019 at 16:11
  • $\begingroup$ Still not clear at all. $\endgroup$
    – Fedor Petrov
    Jan 22, 2019 at 17:22
  • 1
    $\begingroup$ @Mike yes, the question I wrote clearly mentioned regular $\endgroup$
    – vidyarthi
    Jan 22, 2019 at 17:48
  • 1
    $\begingroup$ @Mike oh! sorry, again edited. $\endgroup$
    – vidyarthi
    Jan 22, 2019 at 17:51

2 Answers 2

Reset to default
3
$\begingroup$

No it is not always possible to total color a bipartite graph with $\Delta+1$ colors, even with the given restrictions on $\Delta$ and the number of vertices. This is a counterexample. Let $G$ be a complete bipartite graph with $n$ vertices on each side, where $n$ can be any integer you want as long as it is sufficiently large. [So the degree of each vertex is $n$.]

Suppose there were a proper total coloring $\chi$ using only $n+1$ colors, Let $X$ and $Y$ be the parts of $G$ [to be clear $X$ and $Y$ are sets of vertices], and let $X_{n+1}$ be the entire subset of $X$ that is colored with the $(n+1)$-st colour by $\chi$, and assume WLOG that $X_{n+1}$ is nonempty. Next, let $E_{n+1}$ be the subset of edges colored with the $(n+1)$-st color by this proper total coloring $\chi$. Then $E_{n+1}$ is a matching of cardinality $|X|-|X_{n+1}|=|Y|-|X_{n+1}| < |Y|$. So let $U$ be a subset of $Y$ not incident to an edge in $E_{n+1}$. Then as $G$ is a complete graph, every vertex in $U$ is adjacent to a vertex in $X_{n+1}$, so no vertex in $U$ can be colored with the $(n+1)$st color, and furthermore, as every vertex in $U$ is also not incident to an edge in $E_{n+1}$, it follows that for each $u \in U$ there are only $n$ colors to color $u$ and its $n$ edges incident to $U$ with all different colors. This is impossible.

Improve this answer
$\endgroup$
10
  • $\begingroup$ thanks! I thought about it and am now thinking that this is true of every regular bipartite graphs also. What is your opinion? Any counterexample, i.e., any regular bipartite graph of type $1$? $\endgroup$
    – vidyarthi
    Jan 22, 2019 at 19:36
  • $\begingroup$ Well, admittedly my above argument does not carry through if $d<<n$, where $d$ is defined to be the degree and $n$ the number of vertices on each side. In that case $X_{n+1}$ can have only $\lceil \frac{n}{d+1} \rceil d$ neighbours on the other side. If $n=d$ then $\lceil \frac{n}{d+1} \rceil d$ is of course $n$. $\endgroup$
    – Mike
    Jan 22, 2019 at 19:42
  • $\begingroup$ First, by König theorem, every bipartite graph has edge coloring using $\Delta$ colors where $\Delta$ is maximum degree. Now, consider any vertex. Since $\Delta$ colors are used, so we have to use at least one new color. Again, let the graph be regular. Then, any vertex adjacent to the above chosen vertex should also get another color distinct from $\Delta+1$ colors for a total coloring. Hence, we require $\Delta+2$ colors for a total coloring. Is this argument ok? $\endgroup$
    – vidyarthi
    Jan 22, 2019 at 19:48
  • $\begingroup$ Well, suppose $v$ is colored $d+1$ and let $w$ be a neighbor of $v$. Then a priori at least $w$ is allowed to be colored any color besides $d+1$ and the color assigned to the edge $vw$ $\endgroup$
    – Mike
    Jan 22, 2019 at 19:52
  • $\begingroup$ but, what about the edges incident to the vertex $w$? I am talking about regular bipartite here $\endgroup$
    – vidyarthi
    Jan 22, 2019 at 19:56
1
$\begingroup$

Meanwhile for fixed e.g, $d=6$ there are infinite families of $d$-regular bipartite graphs that have a total coloring with $d+1$ (here 7) colors.

Let $X=\{x_0,\ldots, x_{n-1} \}$ and let $Y = \{y_0,\ldots, x_{n-1}\}$, where $n$ is a multiple of 42.

Then $x_j$ and $y_{j'}$ are adjacent if $j-j' \in \{-3,-2,-1,1,2,3\}$ arithmetic done mod $n$.

The colors are the set $\mathbb{F}_7$; the edge $x_jy_{j'}$ is colored $j+j'$ mod 7, while the vertices $y_j$ and $x_j$ are each colored $2j$ mod 7

Improve this answer
$\endgroup$
2
  • $\begingroup$ great and thanks! But, now, this gives rise to another question. Whether we require $n$ to be a multiple of $42$(or $d(d+1)$) or anything lower is sufficient? $\endgroup$
    – vidyarthi
    Jan 23, 2019 at 7:14
  • $\begingroup$ I think the above construction works for $n=7$ also $\endgroup$
    – vidyarthi
    Jan 23, 2019 at 7:57

Your Answer

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

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