Edge coloring of a graph $G$ with node degrees divisible by $p$ and number of edges NOT divisible by $p$
$begingroup$
Given a graph $G=(V,E)$ with node degrees divisible by $p$ and number of edges not divisible by $p$, show that there exists a coloring (using $p$ colors) of the edges such that for every vertex the number of edges incident with that vertex in any two color classes differ by at most one.
Assume $p ge 2$.
This is what I've been able to deduce: let $d_1, d_2,...,d_n$ be the degrees of the $n = |V|$ nodes of $G$. Because $p mid d_1, p mid d_2,...,p mid d_n$, we can conclude that $p mid 2*|E|$. Knowing that $p nmid |E|$, we further conclude that $2 mid p$, so $p$ and $d_1, d_2,...,d_n$ must be even. Having deduced this information, I tend to believe that the coloring must be somehow related to the Euler tour of the graph (because $G$ is an Eulerian graph). But I don't know how to continue my reasoning.
Any help will be strongly appreciated! Thanks!
graph-theory coloring
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
$endgroup$
add a comment |
$begingroup$
Given a graph $G=(V,E)$ with node degrees divisible by $p$ and number of edges not divisible by $p$, show that there exists a coloring (using $p$ colors) of the edges such that for every vertex the number of edges incident with that vertex in any two color classes differ by at most one.
Assume $p ge 2$.
This is what I've been able to deduce: let $d_1, d_2,...,d_n$ be the degrees of the $n = |V|$ nodes of $G$. Because $p mid d_1, p mid d_2,...,p mid d_n$, we can conclude that $p mid 2*|E|$. Knowing that $p nmid |E|$, we further conclude that $2 mid p$, so $p$ and $d_1, d_2,...,d_n$ must be even. Having deduced this information, I tend to believe that the coloring must be somehow related to the Euler tour of the graph (because $G$ is an Eulerian graph). But I don't know how to continue my reasoning.
Any help will be strongly appreciated! Thanks!
graph-theory coloring
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
$endgroup$
4
$begingroup$
"differ by at most one" would in fact imply "do not differ", wouldn't it?
$endgroup$
– Hagen von Eitzen
Jan 10 at 19:22
2
$begingroup$
I believe so. Given a node with degree $d$ and having $p$, each color must appear $d / p$ times. If it does not, then the difference would be at least 2. Is this correct?
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 19:25
$begingroup$
For $p = 2$, I think that I can take the Eulerian tournament and color its edges alternatively with 0s and 1s. But I'm failing to extend this idea for $p gt 2$.
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 21:24
1
$begingroup$
The question as worded isn't correct though: For example, in any 2-coloring of the edges of a 3-cycle($p=2$) there is one vertex that will be incident to 2 edges of the same color, and none of the other color.
$endgroup$
– Mike
Jan 11 at 15:35
$begingroup$
@HagenvonEitzen Yes. Indeed, let $c_1,dots,c_p$ be the set of used colors and $v$ be any vertex of $G$. For any color $c_i$ let $k_i$ be a number of edges incident to $v$ colored with a color $c_i$. There exists a number $k$ such that $k=k_i$ or $k=k_i+1$ for each color $i$. Let $rle p$ be the number of colors $i$ with $k=k_i+1$. Since $requiv sum k_iequiv deg vequiv 0pmod p$, we have $r=0$ or $r=p$. In both cases all $k_i$’s are equal.
$endgroup$
– Alex Ravsky
Jan 14 at 6:24
add a comment |
$begingroup$
Given a graph $G=(V,E)$ with node degrees divisible by $p$ and number of edges not divisible by $p$, show that there exists a coloring (using $p$ colors) of the edges such that for every vertex the number of edges incident with that vertex in any two color classes differ by at most one.
Assume $p ge 2$.
This is what I've been able to deduce: let $d_1, d_2,...,d_n$ be the degrees of the $n = |V|$ nodes of $G$. Because $p mid d_1, p mid d_2,...,p mid d_n$, we can conclude that $p mid 2*|E|$. Knowing that $p nmid |E|$, we further conclude that $2 mid p$, so $p$ and $d_1, d_2,...,d_n$ must be even. Having deduced this information, I tend to believe that the coloring must be somehow related to the Euler tour of the graph (because $G$ is an Eulerian graph). But I don't know how to continue my reasoning.
Any help will be strongly appreciated! Thanks!
graph-theory coloring
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
$endgroup$
Given a graph $G=(V,E)$ with node degrees divisible by $p$ and number of edges not divisible by $p$, show that there exists a coloring (using $p$ colors) of the edges such that for every vertex the number of edges incident with that vertex in any two color classes differ by at most one.
Assume $p ge 2$.
This is what I've been able to deduce: let $d_1, d_2,...,d_n$ be the degrees of the $n = |V|$ nodes of $G$. Because $p mid d_1, p mid d_2,...,p mid d_n$, we can conclude that $p mid 2*|E|$. Knowing that $p nmid |E|$, we further conclude that $2 mid p$, so $p$ and $d_1, d_2,...,d_n$ must be even. Having deduced this information, I tend to believe that the coloring must be somehow related to the Euler tour of the graph (because $G$ is an Eulerian graph). But I don't know how to continue my reasoning.
Any help will be strongly appreciated! Thanks!
graph-theory coloring
graph-theory coloring
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
asked Jan 10 at 19:17
Răzvan-Andrei CiocoiuRăzvan-Andrei Ciocoiu
576
576
4
$begingroup$
"differ by at most one" would in fact imply "do not differ", wouldn't it?
$endgroup$
– Hagen von Eitzen
Jan 10 at 19:22
2
$begingroup$
I believe so. Given a node with degree $d$ and having $p$, each color must appear $d / p$ times. If it does not, then the difference would be at least 2. Is this correct?
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 19:25
$begingroup$
For $p = 2$, I think that I can take the Eulerian tournament and color its edges alternatively with 0s and 1s. But I'm failing to extend this idea for $p gt 2$.
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 21:24
1
$begingroup$
The question as worded isn't correct though: For example, in any 2-coloring of the edges of a 3-cycle($p=2$) there is one vertex that will be incident to 2 edges of the same color, and none of the other color.
$endgroup$
– Mike
Jan 11 at 15:35
$begingroup$
@HagenvonEitzen Yes. Indeed, let $c_1,dots,c_p$ be the set of used colors and $v$ be any vertex of $G$. For any color $c_i$ let $k_i$ be a number of edges incident to $v$ colored with a color $c_i$. There exists a number $k$ such that $k=k_i$ or $k=k_i+1$ for each color $i$. Let $rle p$ be the number of colors $i$ with $k=k_i+1$. Since $requiv sum k_iequiv deg vequiv 0pmod p$, we have $r=0$ or $r=p$. In both cases all $k_i$’s are equal.
$endgroup$
– Alex Ravsky
Jan 14 at 6:24
add a comment |
4
$begingroup$
"differ by at most one" would in fact imply "do not differ", wouldn't it?
$endgroup$
– Hagen von Eitzen
Jan 10 at 19:22
2
$begingroup$
I believe so. Given a node with degree $d$ and having $p$, each color must appear $d / p$ times. If it does not, then the difference would be at least 2. Is this correct?
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 19:25
$begingroup$
For $p = 2$, I think that I can take the Eulerian tournament and color its edges alternatively with 0s and 1s. But I'm failing to extend this idea for $p gt 2$.
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 21:24
1
$begingroup$
The question as worded isn't correct though: For example, in any 2-coloring of the edges of a 3-cycle($p=2$) there is one vertex that will be incident to 2 edges of the same color, and none of the other color.
$endgroup$
– Mike
Jan 11 at 15:35
$begingroup$
@HagenvonEitzen Yes. Indeed, let $c_1,dots,c_p$ be the set of used colors and $v$ be any vertex of $G$. For any color $c_i$ let $k_i$ be a number of edges incident to $v$ colored with a color $c_i$. There exists a number $k$ such that $k=k_i$ or $k=k_i+1$ for each color $i$. Let $rle p$ be the number of colors $i$ with $k=k_i+1$. Since $requiv sum k_iequiv deg vequiv 0pmod p$, we have $r=0$ or $r=p$. In both cases all $k_i$’s are equal.
$endgroup$
– Alex Ravsky
Jan 14 at 6:24
4
4
$begingroup$
"differ by at most one" would in fact imply "do not differ", wouldn't it?
$endgroup$
– Hagen von Eitzen
Jan 10 at 19:22
$begingroup$
"differ by at most one" would in fact imply "do not differ", wouldn't it?
$endgroup$
– Hagen von Eitzen
Jan 10 at 19:22
2
2
$begingroup$
I believe so. Given a node with degree $d$ and having $p$, each color must appear $d / p$ times. If it does not, then the difference would be at least 2. Is this correct?
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 19:25
$begingroup$
I believe so. Given a node with degree $d$ and having $p$, each color must appear $d / p$ times. If it does not, then the difference would be at least 2. Is this correct?
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 19:25
$begingroup$
For $p = 2$, I think that I can take the Eulerian tournament and color its edges alternatively with 0s and 1s. But I'm failing to extend this idea for $p gt 2$.
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 21:24
$begingroup$
For $p = 2$, I think that I can take the Eulerian tournament and color its edges alternatively with 0s and 1s. But I'm failing to extend this idea for $p gt 2$.
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 21:24
1
1
$begingroup$
The question as worded isn't correct though: For example, in any 2-coloring of the edges of a 3-cycle($p=2$) there is one vertex that will be incident to 2 edges of the same color, and none of the other color.
$endgroup$
– Mike
Jan 11 at 15:35
$begingroup$
The question as worded isn't correct though: For example, in any 2-coloring of the edges of a 3-cycle($p=2$) there is one vertex that will be incident to 2 edges of the same color, and none of the other color.
$endgroup$
– Mike
Jan 11 at 15:35
$begingroup$
@HagenvonEitzen Yes. Indeed, let $c_1,dots,c_p$ be the set of used colors and $v$ be any vertex of $G$. For any color $c_i$ let $k_i$ be a number of edges incident to $v$ colored with a color $c_i$. There exists a number $k$ such that $k=k_i$ or $k=k_i+1$ for each color $i$. Let $rle p$ be the number of colors $i$ with $k=k_i+1$. Since $requiv sum k_iequiv deg vequiv 0pmod p$, we have $r=0$ or $r=p$. In both cases all $k_i$’s are equal.
$endgroup$
– Alex Ravsky
Jan 14 at 6:24
$begingroup$
@HagenvonEitzen Yes. Indeed, let $c_1,dots,c_p$ be the set of used colors and $v$ be any vertex of $G$. For any color $c_i$ let $k_i$ be a number of edges incident to $v$ colored with a color $c_i$. There exists a number $k$ such that $k=k_i$ or $k=k_i+1$ for each color $i$. Let $rle p$ be the number of colors $i$ with $k=k_i+1$. Since $requiv sum k_iequiv deg vequiv 0pmod p$, we have $r=0$ or $r=p$. In both cases all $k_i$’s are equal.
$endgroup$
– Alex Ravsky
Jan 14 at 6:24
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3069070%2fedge-coloring-of-a-graph-g-with-node-degrees-divisible-by-p-and-number-of-ed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3069070%2fedge-coloring-of-a-graph-g-with-node-degrees-divisible-by-p-and-number-of-ed%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
4
$begingroup$
"differ by at most one" would in fact imply "do not differ", wouldn't it?
$endgroup$
– Hagen von Eitzen
Jan 10 at 19:22
2
$begingroup$
I believe so. Given a node with degree $d$ and having $p$, each color must appear $d / p$ times. If it does not, then the difference would be at least 2. Is this correct?
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 19:25
$begingroup$
For $p = 2$, I think that I can take the Eulerian tournament and color its edges alternatively with 0s and 1s. But I'm failing to extend this idea for $p gt 2$.
$endgroup$
– Răzvan-Andrei Ciocoiu
Jan 10 at 21:24
1
$begingroup$
The question as worded isn't correct though: For example, in any 2-coloring of the edges of a 3-cycle($p=2$) there is one vertex that will be incident to 2 edges of the same color, and none of the other color.
$endgroup$
– Mike
Jan 11 at 15:35
$begingroup$
@HagenvonEitzen Yes. Indeed, let $c_1,dots,c_p$ be the set of used colors and $v$ be any vertex of $G$. For any color $c_i$ let $k_i$ be a number of edges incident to $v$ colored with a color $c_i$. There exists a number $k$ such that $k=k_i$ or $k=k_i+1$ for each color $i$. Let $rle p$ be the number of colors $i$ with $k=k_i+1$. Since $requiv sum k_iequiv deg vequiv 0pmod p$, we have $r=0$ or $r=p$. In both cases all $k_i$’s are equal.
$endgroup$
– Alex Ravsky
Jan 14 at 6:24