Deletion-contraction versus addition-identificationOrder of deletion and contraction to form a minorIs a rigid cycle a chordal graph?Find a graph with critical vertices and without critical edges.Deriving deletion-contraction formula from Subgraph Expansion of Chromatic PolynomialIs the Wikipedia article about chordal graphs incorrect?Find the chromatic polynomial to this graphDeletion-Contraction to Find Number of Spanning Trees, $tau(G)$.Class of chordal graphs is closed under edge-contractionDefinition of weakly chordal graphs and difference to Berge graphProof that the chromatic polynomial of a simple graph G with n vertices has degree n.
Why can't we play rap on piano?
How can I prevent hyper evolved versions of regular creatures from wiping out their cousins?
Can I use a neutral wire from another outlet to repair a broken neutral?
How much of data wrangling is a data scientist's job?
Could gravitational lensing be used to protect a spaceship from a laser?
Can a rocket refuel on Mars from water?
How can I make my BBEG immortal short of making them a Lich or Vampire?
prove that the matrix A is diagonalizable
How can saying a song's name be a copyright violation?
How do I write bicross product symbols in latex?
What does it mean to describe someone as a butt steak?
How do I find out when a node was added to an availability group?
Blender 2.8 I can't see vertices, edges or faces in edit mode
Why does Arabsat 6A need a Falcon Heavy to launch
How badly should I try to prevent a user from XSSing themselves?
Can I make "comment-region" comment empty lines?
Why does Kotter return in Welcome Back Kotter
Is it unprofessional to ask if a job posting on GlassDoor is real?
Where does SFDX store details about scratch orgs?
Increase size of symbol intercal when in superscript position
Why is the ratio of two extensive quantities always intensive?
How to model explosives?
Why is Collection not simply treated as Collection<?>
Can I ask the recruiters in my resume to put the reason why I am rejected?
Deletion-contraction versus addition-identification
Order of deletion and contraction to form a minorIs a rigid cycle a chordal graph?Find a graph with critical vertices and without critical edges.Deriving deletion-contraction formula from Subgraph Expansion of Chromatic PolynomialIs the Wikipedia article about chordal graphs incorrect?Find the chromatic polynomial to this graphDeletion-Contraction to Find Number of Spanning Trees, $tau(G)$.Class of chordal graphs is closed under edge-contractionDefinition of weakly chordal graphs and difference to Berge graphProof that the chromatic polynomial of a simple graph G with n vertices has degree n.
$begingroup$
Short version: there are two common formulas for computing the chromatic polynomial of a graph. They go by the names, deletion-contraction and addition-identification. They are equivalent, mathematically, but differ in their application. I know graphs for which a-i is more efficient than d-c. Are there graphs for which d-c is more efficient than a-i?
Long version: Let $G$ be a graph. The chromatic polynomial $P(G,k)$ gives the number of ways to color the vertices of $G$, if $k$ colors are available, and no two adjacent vertices get the same color. If $G$ is chordal (that is, if every cycle in $G$ has a chord, a pair of vertices adjacent in $G$ but not adjacent in the cycle), then you can compute $P(G,k)$ by "following your nose". If $G$ is not chordal, then you can use either of these formulas, repeatedly if necessary, to reduce to the case of chordal graphs: $$P(G,k)=P(G-e,k)-P(G/e,k)tag1$$ $$P(G,k)=P(G+e,k)+P(G/e,k)tag2$$ (1) is called "deletion-contraction"; $e$ is an arbitrary edge of $G$, $G-e$ is what's left when you delete $e$ from $G$, and $G/e$ is what results when you contract $e$ to a point. (2) is called "addition-identification"; $e$ is an edge not in $G$, $G+e$ is the result of adding $e$ to $G$, and $G/e$ is what happens when you identify the endpoints of $e$. (1) and (2) are mathematically equivalent, but differ in the way they are applied, as (1) deletes an edge from $G$, while (2) adds an edge to $G$.
I know examples where (2) is more efficient than (1). E.g., if $G$ is $K_2,3$ (each of two vertices $A,B$ joined to each of three vertices $X,Y,Z$), then any edge-deletion yields a non-chordal graph, so a second application of (1) is called for, but if $e$ in (2) joins $A$ and $B$ then $G+e$ and $G/e$ are both chordal and no further reduction is needed.
I know many examples where (1) and (2) are equally efficient (e.g., if $G$ is a 4-cycle). I don't know any example where (1) is strictly more efficient than (2) (and occasionally I think I can prove this can't happen). Is there a graph that requires fewer iterations of (1) than of (2)?
graph-theory
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
$endgroup$
This question has an open bounty worth +50
reputation from Gerry Myerson ending ending at 2019-04-05 01:08:01Z">in 3 hours.
This question has not received enough attention.
Actually, I don't know how much attention this question has drawn, but I can see it hasn't drawn any answers, and I'd like to get one.
add a comment |
$begingroup$
Short version: there are two common formulas for computing the chromatic polynomial of a graph. They go by the names, deletion-contraction and addition-identification. They are equivalent, mathematically, but differ in their application. I know graphs for which a-i is more efficient than d-c. Are there graphs for which d-c is more efficient than a-i?
Long version: Let $G$ be a graph. The chromatic polynomial $P(G,k)$ gives the number of ways to color the vertices of $G$, if $k$ colors are available, and no two adjacent vertices get the same color. If $G$ is chordal (that is, if every cycle in $G$ has a chord, a pair of vertices adjacent in $G$ but not adjacent in the cycle), then you can compute $P(G,k)$ by "following your nose". If $G$ is not chordal, then you can use either of these formulas, repeatedly if necessary, to reduce to the case of chordal graphs: $$P(G,k)=P(G-e,k)-P(G/e,k)tag1$$ $$P(G,k)=P(G+e,k)+P(G/e,k)tag2$$ (1) is called "deletion-contraction"; $e$ is an arbitrary edge of $G$, $G-e$ is what's left when you delete $e$ from $G$, and $G/e$ is what results when you contract $e$ to a point. (2) is called "addition-identification"; $e$ is an edge not in $G$, $G+e$ is the result of adding $e$ to $G$, and $G/e$ is what happens when you identify the endpoints of $e$. (1) and (2) are mathematically equivalent, but differ in the way they are applied, as (1) deletes an edge from $G$, while (2) adds an edge to $G$.
I know examples where (2) is more efficient than (1). E.g., if $G$ is $K_2,3$ (each of two vertices $A,B$ joined to each of three vertices $X,Y,Z$), then any edge-deletion yields a non-chordal graph, so a second application of (1) is called for, but if $e$ in (2) joins $A$ and $B$ then $G+e$ and $G/e$ are both chordal and no further reduction is needed.
I know many examples where (1) and (2) are equally efficient (e.g., if $G$ is a 4-cycle). I don't know any example where (1) is strictly more efficient than (2) (and occasionally I think I can prove this can't happen). Is there a graph that requires fewer iterations of (1) than of (2)?
graph-theory
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
$endgroup$
This question has an open bounty worth +50
reputation from Gerry Myerson ending ending at 2019-04-05 01:08:01Z">in 3 hours.
This question has not received enough attention.
Actually, I don't know how much attention this question has drawn, but I can see it hasn't drawn any answers, and I'd like to get one.
$begingroup$
I would use (1) to derive the formula for $P(C_n,k)$ and I never thought about doing it another way. How does it work out using (2)?
$endgroup$
– bof
May 27 '16 at 3:13
$begingroup$
@bof, I take it that by $C_n$ you mean an $n$-cycle. If you let $e$ be an edge joining two vertices that are "adjacent-but-one", then using (2) you get $P(C_n,k)=(k-2)P(C_n-1,k)+(k-1)P(C_n-2,k)$.
$endgroup$
– Gerry Myerson
May 27 '16 at 4:07
add a comment |
$begingroup$
Short version: there are two common formulas for computing the chromatic polynomial of a graph. They go by the names, deletion-contraction and addition-identification. They are equivalent, mathematically, but differ in their application. I know graphs for which a-i is more efficient than d-c. Are there graphs for which d-c is more efficient than a-i?
Long version: Let $G$ be a graph. The chromatic polynomial $P(G,k)$ gives the number of ways to color the vertices of $G$, if $k$ colors are available, and no two adjacent vertices get the same color. If $G$ is chordal (that is, if every cycle in $G$ has a chord, a pair of vertices adjacent in $G$ but not adjacent in the cycle), then you can compute $P(G,k)$ by "following your nose". If $G$ is not chordal, then you can use either of these formulas, repeatedly if necessary, to reduce to the case of chordal graphs: $$P(G,k)=P(G-e,k)-P(G/e,k)tag1$$ $$P(G,k)=P(G+e,k)+P(G/e,k)tag2$$ (1) is called "deletion-contraction"; $e$ is an arbitrary edge of $G$, $G-e$ is what's left when you delete $e$ from $G$, and $G/e$ is what results when you contract $e$ to a point. (2) is called "addition-identification"; $e$ is an edge not in $G$, $G+e$ is the result of adding $e$ to $G$, and $G/e$ is what happens when you identify the endpoints of $e$. (1) and (2) are mathematically equivalent, but differ in the way they are applied, as (1) deletes an edge from $G$, while (2) adds an edge to $G$.
I know examples where (2) is more efficient than (1). E.g., if $G$ is $K_2,3$ (each of two vertices $A,B$ joined to each of three vertices $X,Y,Z$), then any edge-deletion yields a non-chordal graph, so a second application of (1) is called for, but if $e$ in (2) joins $A$ and $B$ then $G+e$ and $G/e$ are both chordal and no further reduction is needed.
I know many examples where (1) and (2) are equally efficient (e.g., if $G$ is a 4-cycle). I don't know any example where (1) is strictly more efficient than (2) (and occasionally I think I can prove this can't happen). Is there a graph that requires fewer iterations of (1) than of (2)?
graph-theory
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
$endgroup$
Short version: there are two common formulas for computing the chromatic polynomial of a graph. They go by the names, deletion-contraction and addition-identification. They are equivalent, mathematically, but differ in their application. I know graphs for which a-i is more efficient than d-c. Are there graphs for which d-c is more efficient than a-i?
Long version: Let $G$ be a graph. The chromatic polynomial $P(G,k)$ gives the number of ways to color the vertices of $G$, if $k$ colors are available, and no two adjacent vertices get the same color. If $G$ is chordal (that is, if every cycle in $G$ has a chord, a pair of vertices adjacent in $G$ but not adjacent in the cycle), then you can compute $P(G,k)$ by "following your nose". If $G$ is not chordal, then you can use either of these formulas, repeatedly if necessary, to reduce to the case of chordal graphs: $$P(G,k)=P(G-e,k)-P(G/e,k)tag1$$ $$P(G,k)=P(G+e,k)+P(G/e,k)tag2$$ (1) is called "deletion-contraction"; $e$ is an arbitrary edge of $G$, $G-e$ is what's left when you delete $e$ from $G$, and $G/e$ is what results when you contract $e$ to a point. (2) is called "addition-identification"; $e$ is an edge not in $G$, $G+e$ is the result of adding $e$ to $G$, and $G/e$ is what happens when you identify the endpoints of $e$. (1) and (2) are mathematically equivalent, but differ in the way they are applied, as (1) deletes an edge from $G$, while (2) adds an edge to $G$.
I know examples where (2) is more efficient than (1). E.g., if $G$ is $K_2,3$ (each of two vertices $A,B$ joined to each of three vertices $X,Y,Z$), then any edge-deletion yields a non-chordal graph, so a second application of (1) is called for, but if $e$ in (2) joins $A$ and $B$ then $G+e$ and $G/e$ are both chordal and no further reduction is needed.
I know many examples where (1) and (2) are equally efficient (e.g., if $G$ is a 4-cycle). I don't know any example where (1) is strictly more efficient than (2) (and occasionally I think I can prove this can't happen). Is there a graph that requires fewer iterations of (1) than of (2)?
graph-theory
graph-theory
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
asked May 27 '16 at 3:04
Gerry MyersonGerry Myerson
148k8151305
148k8151305
This question has an open bounty worth +50
reputation from Gerry Myerson ending ending at 2019-04-05 01:08:01Z">in 3 hours.
This question has not received enough attention.
Actually, I don't know how much attention this question has drawn, but I can see it hasn't drawn any answers, and I'd like to get one.
This question has an open bounty worth +50
reputation from Gerry Myerson ending ending at 2019-04-05 01:08:01Z">in 3 hours.
This question has not received enough attention.
Actually, I don't know how much attention this question has drawn, but I can see it hasn't drawn any answers, and I'd like to get one.
$begingroup$
I would use (1) to derive the formula for $P(C_n,k)$ and I never thought about doing it another way. How does it work out using (2)?
$endgroup$
– bof
May 27 '16 at 3:13
$begingroup$
@bof, I take it that by $C_n$ you mean an $n$-cycle. If you let $e$ be an edge joining two vertices that are "adjacent-but-one", then using (2) you get $P(C_n,k)=(k-2)P(C_n-1,k)+(k-1)P(C_n-2,k)$.
$endgroup$
– Gerry Myerson
May 27 '16 at 4:07
add a comment |
$begingroup$
I would use (1) to derive the formula for $P(C_n,k)$ and I never thought about doing it another way. How does it work out using (2)?
$endgroup$
– bof
May 27 '16 at 3:13
$begingroup$
@bof, I take it that by $C_n$ you mean an $n$-cycle. If you let $e$ be an edge joining two vertices that are "adjacent-but-one", then using (2) you get $P(C_n,k)=(k-2)P(C_n-1,k)+(k-1)P(C_n-2,k)$.
$endgroup$
– Gerry Myerson
May 27 '16 at 4:07
$begingroup$
I would use (1) to derive the formula for $P(C_n,k)$ and I never thought about doing it another way. How does it work out using (2)?
$endgroup$
– bof
May 27 '16 at 3:13
$begingroup$
I would use (1) to derive the formula for $P(C_n,k)$ and I never thought about doing it another way. How does it work out using (2)?
$endgroup$
– bof
May 27 '16 at 3:13
$begingroup$
@bof, I take it that by $C_n$ you mean an $n$-cycle. If you let $e$ be an edge joining two vertices that are "adjacent-but-one", then using (2) you get $P(C_n,k)=(k-2)P(C_n-1,k)+(k-1)P(C_n-2,k)$.
$endgroup$
– Gerry Myerson
May 27 '16 at 4:07
$begingroup$
@bof, I take it that by $C_n$ you mean an $n$-cycle. If you let $e$ be an edge joining two vertices that are "adjacent-but-one", then using (2) you get $P(C_n,k)=(k-2)P(C_n-1,k)+(k-1)P(C_n-2,k)$.
$endgroup$
– Gerry Myerson
May 27 '16 at 4:07
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%2f1801643%2fdeletion-contraction-versus-addition-identification%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%2f1801643%2fdeletion-contraction-versus-addition-identification%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
$begingroup$
I would use (1) to derive the formula for $P(C_n,k)$ and I never thought about doing it another way. How does it work out using (2)?
$endgroup$
– bof
May 27 '16 at 3:13
$begingroup$
@bof, I take it that by $C_n$ you mean an $n$-cycle. If you let $e$ be an edge joining two vertices that are "adjacent-but-one", then using (2) you get $P(C_n,k)=(k-2)P(C_n-1,k)+(k-1)P(C_n-2,k)$.
$endgroup$
– Gerry Myerson
May 27 '16 at 4:07