Skip to main content

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 coveringcoloring $\chi$. Then $E_{n+1}$ is a matching of cardinality $|X|-|X_{n+1}|$ $=|Y|-|X_{n+1}| < |Y|$$|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.

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 covering $\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.

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.

added 24 characters in body
Source Link
Mike
  • 1k
  • 6
  • 14

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 covering $\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.

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 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, 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 covering. 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.

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 covering $\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.

Source Link
Mike
  • 1k
  • 6
  • 14

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 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, 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 covering. 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.