Mixing
Is it possible to start with a partially colored graph for a graph $G$ and complete it into a coloring with...
up vote
1
down vote
favorite
I was trying this problem: A question about graph coloring and partition of graph
and had an idea which is:
We know that $chi(G[X])le k$ and $chi(G[Y])le k$.
and $E(X,Y)le k-1$. Color $X$ in $G[X]$ using k colors, say${1,2,...,k}$. Then connect the two partion with the $k-1$ edges between them. Because a vertex in $Y$ has at most $k-1$ neighbours in $|X|$, It is adjacent to at most $k-1$ different colored vertices. So pick a vertex $v_1$ in $Y$ whose number of neighbors in $X$ is the maximum among all vertices in $Y$. It is adjacent to at most $k-1$ colored vertices so we can color it using the one of ${1,2...,k}$. Now pick another vertex $v_2$ in $Y$ with neighbour in $|X|$ maximum among all vertices in $X-{v_1}$, It is adjacent to at most $k-2$ edges in $X$(because $v_1$ is adjacent to at least one in $X$). It could also be adjacent to $v_1$, but in any case, it has at most $k-1$ colored neighbors, so then you can color it using one of ${1,2,...,k}$. Keep this coloring process going until you colored all vertices in $Y$ with neighbours in $X$. Now it would be nice if we can complete this partial coloring into a coloring using $chi(G[Y])$ colors. Because then that solves the problem.
graph-theory
asked 2 days ago
mathnoob
65411
add a comment |
up vote
1
down vote
favorite
I was trying this problem: A question about graph coloring and partition of graph
and had an idea which is:
We know that $chi(G[X])le k$ and $chi(G[Y])le k$.
and $E(X,Y)le k-1$. Color $X$ in $G[X]$ using k colors, say${1,2,...,k}$. Then connect the two partion with the $k-1$ edges between them. Because a vertex in $Y$ has at most $k-1$ neighbours in $|X|$, It is adjacent to at most $k-1$ different colored vertices. So pick a vertex $v_1$ in $Y$ whose number of neighbors in $X$ is the maximum among all vertices in $Y$. It is adjacent to at most $k-1$ colored vertices so we can color it using the one of ${1,2...,k}$. Now pick another vertex $v_2$ in $Y$ with neighbour in $|X|$ maximum among all vertices in $X-{v_1}$, It is adjacent to at most $k-2$ edges in $X$(because $v_1$ is adjacent to at least one in $X$). It could also be adjacent to $v_1$, but in any case, it has at most $k-1$ colored neighbors, so then you can color it using one of ${1,2,...,k}$. Keep this coloring process going until you colored all vertices in $Y$ with neighbours in $X$. Now it would be nice if we can complete this partial coloring into a coloring using $chi(G[Y])$ colors. Because then that solves the problem.
graph-theory
asked 2 days ago
mathnoob
65411
1
If you look at the graph in the shape $N$, this is bipartite and hence $2$-colorable, but if you color the upper right corner and the lower left corner with the same color, you can't extend this to a $2$-coloring.
– Matt Samuel
2 days ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I was trying this problem: A question about graph coloring and partition of graph
and had an idea which is:
We know that $chi(G[X])le k$ and $chi(G[Y])le k$.
and $E(X,Y)le k-1$. Color $X$ in $G[X]$ using k colors, say${1,2,...,k}$. Then connect the two partion with the $k-1$ edges between them. Because a vertex in $Y$ has at most $k-1$ neighbours in $|X|$, It is adjacent to at most $k-1$ different colored vertices. So pick a vertex $v_1$ in $Y$ whose number of neighbors in $X$ is the maximum among all vertices in $Y$. It is adjacent to at most $k-1$ colored vertices so we can color it using the one of ${1,2...,k}$. Now pick another vertex $v_2$ in $Y$ with neighbour in $|X|$ maximum among all vertices in $X-{v_1}$, It is adjacent to at most $k-2$ edges in $X$(because $v_1$ is adjacent to at least one in $X$). It could also be adjacent to $v_1$, but in any case, it has at most $k-1$ colored neighbors, so then you can color it using one of ${1,2,...,k}$. Keep this coloring process going until you colored all vertices in $Y$ with neighbours in $X$. Now it would be nice if we can complete this partial coloring into a coloring using $chi(G[Y])$ colors. Because then that solves the problem.
graph-theory
asked 2 days ago
mathnoob
65411
I was trying this problem: A question about graph coloring and partition of graph
and had an idea which is:
We know that $chi(G[X])le k$ and $chi(G[Y])le k$.
and $E(X,Y)le k-1$. Color $X$ in $G[X]$ using k colors, say${1,2,...,k}$. Then connect the two partion with the $k-1$ edges between them. Because a vertex in $Y$ has at most $k-1$ neighbours in $|X|$, It is adjacent to at most $k-1$ different colored vertices. So pick a vertex $v_1$ in $Y$ whose number of neighbors in $X$ is the maximum among all vertices in $Y$. It is adjacent to at most $k-1$ colored vertices so we can color it using the one of ${1,2...,k}$. Now pick another vertex $v_2$ in $Y$ with neighbour in $|X|$ maximum among all vertices in $X-{v_1}$, It is adjacent to at most $k-2$ edges in $X$(because $v_1$ is adjacent to at least one in $X$). It could also be adjacent to $v_1$, but in any case, it has at most $k-1$ colored neighbors, so then you can color it using one of ${1,2,...,k}$. Keep this coloring process going until you colored all vertices in $Y$ with neighbours in $X$. Now it would be nice if we can complete this partial coloring into a coloring using $chi(G[Y])$ colors. Because then that solves the problem.
graph-theory
graph-theory
asked 2 days ago
mathnoob
65411
asked 2 days ago
mathnoob
65411
asked 2 days ago
mathnoob
65411
asked 2 days ago
mathnoob
65411
asked 2 days ago
mathnoob
65411
65411
1
If you look at the graph in the shape $N$, this is bipartite and hence $2$-colorable, but if you color the upper right corner and the lower left corner with the same color, you can't extend this to a $2$-coloring.
– Matt Samuel
2 days ago
add a comment |
1
If you look at the graph in the shape $N$, this is bipartite and hence $2$-colorable, but if you color the upper right corner and the lower left corner with the same color, you can't extend this to a $2$-coloring.
– Matt Samuel
2 days ago
1
1
If you look at the graph in the shape $N$, this is bipartite and hence $2$-colorable, but if you color the upper right corner and the lower left corner with the same color, you can't extend this to a $2$-coloring.
– Matt Samuel
2 days ago
If you look at the graph in the shape $N$, this is bipartite and hence $2$-colorable, but if you color the upper right corner and the lower left corner with the same color, you can't extend this to a $2$-coloring.
– Matt Samuel
2 days ago
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005657%2fis-it-possible-to-start-with-a-partially-colored-graph-for-a-graph-g-and-compl%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
If you look at the graph in the shape $N$, this is bipartite and hence $2$-colorable, but if you color the upper right corner and the lower left corner with the same color, you can't extend this to a $2$-coloring.
– Matt Samuel
2 days ago