Return to Question

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that induce disjoint triangles (3-circuits). Note $G$ is 4-regular.

UPDATED QUESTION (2019 may 17):

QUESTION: Is $G$ class 1, that is, can it be edge-4-colored, if it has an even number of triangles?

ANSWER: (2019 november 23) NOT in general ... see answer 2. It remains to find an example which is 3 connected. Also, the complexity of finding the chromatic index of these graphs is to be determined ... it should be NP complete.

NEW UPDATE (2019 may 20 b): A question of which an affirmative answer implies an affirmative answer to our original question: Does $G$ have a Hamiltonian factorization, that is, are there two edge disjoint spanning cycles in $G$. I haven’t checked this with a computer, but it seems to hold for the small cases. UPDATE: I have now this working in a computer ... I haven’t tested many graphs, but the few I have tested, including some larger ones, seem to have (I write seem because I need to verify my code) Hamiltonian decompositions, including those of odd order. Next I will put this in a loop and test LOTS of random examples. SEE ANSWER FOR PICTURE ..

NOTE: Regarding the Hamiltonian decompositions, it was an open problem until 1997 whether CT graphs had a Hamiltonian circuit other than the obvious one. This was settled affirmatively by Thomassen. But the computer says that, for example, a random CT graph with 12 triangles has about 300 000 (not exact) distinct Hamiltonian circuits. I need to make the tests with a lot more graphs to determine some kind of average.

(SIDE) FACT : If $G$ has an odd number of triangles then it is class 2. This is because a cycle plus triangles graph with an odd number of triangles is a regular graph of odd order ... all such graphs are class 2 (suppose it is class 1 ... then each vertex is incident with an edge of each color. But the edges of a given color are independent, so they are incident with an even number of vertices, while there is an odd number of vertices, contradiction).

Cycle plus triangles graphs became well known when Erdös posed the “cycle plus triangles problem” (whether such graphs are vertex-3-colorable). This was solved affirmatively by Fleishner and Stiebitz using the Alon-Tarsi theorem, and later Sachs, inductively.

In the generalization of this question to “cycle plus even $k$-cliques” (I hope it is clear what this means) the answer is that they are all class 1, as you can edge color the edges of the $k$-cliques with $k$-1 colors, and use two remaining colors for the edges of the even cycle in the ($k$+1)-regular graph.

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that induce disjoint triangles (3-circuits). Note $G$ is 4-regular.

UPDATED QUESTION (2019 may 17):

QUESTION: Is $G$ class 1, that is, can it be edge-4-colored, if it has an even number of triangles?

ANSWER: (2019 november 23) NOT in general ... see answer 2. It remains to find an example which is 3 connected. Also, the complexity of finding the chromatic index of these graphs is to be determined ... it should be NP complete, perhaps???

NEW UPDATE (2019 may 20 b): A question of which an affirmative answer implies an affirmative answer to our original question: Does $G$ have a Hamiltonian factorization, that is, are there two edge disjoint spanning cycles in $G$. I haven’t checked this with a computer, but it seems to hold for the small cases. UPDATE: I have now this working in a computer ... I haven’t tested many graphs, but the few I have tested, including some larger ones, seem to have (I write seem because I need to verify my code) Hamiltonian decompositions, including those of odd order. Next I will put this in a loop and test LOTS of random examples. SEE ANSWER FOR PICTURE ..

NOTE: Regarding the Hamiltonian decompositions, it was an open problem until 1997 whether CT graphs had a Hamiltonian circuit other than the obvious one. This was settled affirmatively by Thomassen. But the computer says that, for example, a random CT graph with 12 triangles has about 300 000 (not exact) distinct Hamiltonian circuits. I need to make the tests with a lot more graphs to determine some kind of average.

(SIDE) FACT : If $G$ has an odd number of triangles then it is class 2. This is because a cycle plus triangles graph with an odd number of triangles is a regular graph of odd order ... all such graphs are class 2 (suppose it is class 1 ... then each vertex is incident with an edge of each color. But the edges of a given color are independent, so they are incident with an even number of vertices, while there is an odd number of vertices, contradiction).

Cycle plus triangles graphs became well known when Erdös posed the “cycle plus triangles problem” (whether such graphs are vertex-3-colorable). This was solved affirmatively by Fleishner and Stiebitz using the Alon-Tarsi theorem, and later Sachs, inductively.

In the generalization of this question to “cycle plus even $k$-cliques” (I hope it is clear what this means) the answer is that they are all class 1, as you can edge color the edges of the $k$-cliques with $k$-1 colors, and use two remaining colors for the edges of the even cycle in the ($k$+1)-regular graph.

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that induce disjoint triangles (3-circuits). Note $G$ is 4-regular.

UPDATED QUESTION (2019 may 17):

QUESTION: Is $G$ class 1, that is, can it be edge-4-colored, if it has an even number of triangles?

ANSWER: (2019 november 23) NOT in general ... see answer 2, to be posted in a few minutes. It remains to find a counterexample which is 3 connected. Also, the complexity of this problem is to be determined ... it should be NP complete.

NEW UPDATE (2019 may 20 b): A question of which an affirmative answer implies an affirmative answer to our original question: Does $G$ have a Hamiltonian factorization, that is, are there two edge disjoint spanning cycles in $G$. I haven’t checked this with a computer, but it seems to hold for the small cases. UPDATE: I have now this working in a computer ... I haven’t tested many graphs, but the few I have tested, including some larger ones, seem to have (I write seem because I need to verify my code) Hamiltonian decompositions, including those of odd order. Next I will put this in a loop and test LOTS of random examples. SEE ANSWER FOR PICTURE ..

NOTE: Regarding the Hamiltonian decompositions, it was an open problem until 1997 whether CT graphs had a Hamiltonian circuit other than the obvious one. This was settled affirmatively by Thomassen. But the computer says that, for example, a random CT graph with 12 triangles has about 300 000 (not exact) distinct Hamiltonian circuits. I need to make the tests with a lot more graphs to determine some kind of average.

(SIDE) FACT : If $G$ has an odd number of triangles then it is class 2. This is because a cycle plus triangles graph with an odd number of triangles is a regular graph of odd order ... all such graphs are class 2 (suppose it is class 1 ... then each vertex is incident with an edge of each color. But the edges of a given color are independent, so they are incident with an even number of vertices, while there is an odd number of vertices, contradiction).

Cycle plus triangles graphs became well known when Erdös posed the “cycle plus triangles problem” (whether such graphs are vertex-3-colorable). This was solved affirmatively by Fleishner and Stiebitz using the Alon-Tarsi theorem, and later Sachs, inductively.

In the generalization of this question to “cycle plus even $k$-cliques” (I hope it is clear what this means) the answer is that they are all class 1, as you can edge color the edges of the $k$-cliques with $k$-1 colors, and use two remaining colors for the edges of the even cycle in the ($k$+1)-regular graph.

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that induce disjoint triangles (3-circuits). Note $G$ is 4-regular.

UPDATED QUESTION (2019 may 17):

QUESTION: Is $G$ class 1, that is, can it be edge-4-colored, if it has an even number of triangles?

ANSWER: (2019 november 23) NOT in general ... see answer 2. It remains to find an example which is 3 connected. Also, the complexity of finding the chromatic index of these graphs is to be determined ... it should be NP complete.

NEW UPDATE (2019 may 20 b): A question of which an affirmative answer implies an affirmative answer to our original question: Does $G$ have a Hamiltonian factorization, that is, are there two edge disjoint spanning cycles in $G$. I haven’t checked this with a computer, but it seems to hold for the small cases. UPDATE: I have now this working in a computer ... I haven’t tested many graphs, but the few I have tested, including some larger ones, seem to have (I write seem because I need to verify my code) Hamiltonian decompositions, including those of odd order. Next I will put this in a loop and test LOTS of random examples. SEE ANSWER FOR PICTURE ..

NOTE: Regarding the Hamiltonian decompositions, it was an open problem until 1997 whether CT graphs had a Hamiltonian circuit other than the obvious one. This was settled affirmatively by Thomassen. But the computer says that, for example, a random CT graph with 12 triangles has about 300 000 (not exact) distinct Hamiltonian circuits. I need to make the tests with a lot more graphs to determine some kind of average.

(SIDE) FACT : If $G$ has an odd number of triangles then it is class 2. This is because a cycle plus triangles graph with an odd number of triangles is a regular graph of odd order ... all such graphs are class 2 (suppose it is class 1 ... then each vertex is incident with an edge of each color. But the edges of a given color are independent, so they are incident with an even number of vertices, while there is an odd number of vertices, contradiction).

Cycle plus triangles graphs became well known when Erdös posed the “cycle plus triangles problem” (whether such graphs are vertex-3-colorable). This was solved affirmatively by Fleishner and Stiebitz using the Alon-Tarsi theorem, and later Sachs, inductively.

In the generalization of this question to “cycle plus even $k$-cliques” (I hope it is clear what this means) the answer is that they are all class 1, as you can edge color the edges of the $k$-cliques with $k$-1 colors, and use two remaining colors for the edges of the even cycle in the ($k$+1)-regular graph.

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that induce disjoint triangles (3-circuits). Note $G$ is 4-regular.

UPDATED QUESTION (2019 may 17):

QUESTION: Is $G$ class 1, that is, can it be edge-4-colored, if it has an even number of triangles?

NEW UPDATE (2019 may 20 b): A question of which an affirmative answer implies an affirmative answer to our original question: Does $G$ have a Hamiltonian factorization, that is, are there two edge disjoint spanning cycles in $G$. I haven’t checked this with a computer, but it seems to hold for the small cases. UPDATE: I have now this working in a computer ... I haven’t tested many graphs, but the few I have tested, including some larger ones, seem to have (I write seem because I need to verify my code) Hamiltonian decompositions, including those of odd order. Next I will put this in a loop and test LOTS of random examples. SEE ANSWER FOR PICTURE ..

NOTE: Regarding the Hamiltonian decompositions, it was an open problem until 1997 whether CT graphs had a Hamiltonian circuit other than the obvious one. This was settled affirmatively by Thomassen. But the computer says that, for example, a random CT graph with 12 triangles has about 300 000 (not exact) distinct Hamiltonian circuits. I need to make the tests with a lot more graphs to determine some kind of average.

(SIDE) FACT : If $G$ has an odd number of triangles then it is class 2. This is because a cycle plus triangles graph with an odd number of triangles is a regular graph of odd order ... all such graphs are class 2 (suppose it is class 1 ... then each vertex is incident with an edge of each color. But the edges of a given color are independent, so they are incident with an even number of vertices, while there is an odd number of vertices, contradiction).

The hypothesis that C+T graphs which have an even number of triangles are class 1 is supported by computer experiments.

Cycle plus triangles graphs became well known when Erdös posed the “cycle plus triangles problem” (whether such graphs are vertex-3-colorable). This was solved affirmatively by Fleishner and Stiebitz using the Alon-Tarsi theorem, and later Sachs, inductively.

Perhaps the answer to my question above is known, but I am unaware of it.

In the generalization of this question to “cycle plus even $k$-cliques” (I hope it is clear what this means) the answer is that they are all class 1, as you can edge color the edges of the $k$-cliques with $k$-1 colors, and use two remaining colors for the edges of the even cycle in the ($k$+1)-regular graph. It is tantalizing to speculate that a similar answer as the answer for the “cycles plus triangles” case would hold for the general “cycle plus odd cliques” situation, of which the cycle plus triangles is a special case. It would be nice to settle at least this special case with proofs, if it is not settled already.

Let $G$ be a simple “cycle plus triangles” graph, that is, a graph with $3k$ vertices, $k>1$, the edges of which can be partitioned into a set that induces a $3k$-circuit, together with sets that induce disjoint triangles (3-circuits). Note $G$ is 4-regular.

UPDATED QUESTION (2019 may 17):

QUESTION: Is $G$ class 1, that is, can it be edge-4-colored, if it has an even number of triangles?

ANSWER: (2019 november 23) NOT in general ... see answer 2, to be posted in a few minutes. It remains to find a counterexample which is 3 connected. Also, the complexity of this problem is to be determined ... it should be NP complete.

NEW UPDATE (2019 may 20 b): A question of which an affirmative answer implies an affirmative answer to our original question: Does $G$ have a Hamiltonian factorization, that is, are there two edge disjoint spanning cycles in $G$. I haven’t checked this with a computer, but it seems to hold for the small cases. UPDATE: I have now this working in a computer ... I haven’t tested many graphs, but the few I have tested, including some larger ones, seem to have (I write seem because I need to verify my code) Hamiltonian decompositions, including those of odd order. Next I will put this in a loop and test LOTS of random examples. SEE ANSWER FOR PICTURE ..

NOTE: Regarding the Hamiltonian decompositions, it was an open problem until 1997 whether CT graphs had a Hamiltonian circuit other than the obvious one. This was settled affirmatively by Thomassen. But the computer says that, for example, a random CT graph with 12 triangles has about 300 000 (not exact) distinct Hamiltonian circuits. I need to make the tests with a lot more graphs to determine some kind of average.

(SIDE) FACT : If $G$ has an odd number of triangles then it is class 2. This is because a cycle plus triangles graph with an odd number of triangles is a regular graph of odd order ... all such graphs are class 2 (suppose it is class 1 ... then each vertex is incident with an edge of each color. But the edges of a given color are independent, so they are incident with an even number of vertices, while there is an odd number of vertices, contradiction).

Cycle plus triangles graphs became well known when Erdös posed the “cycle plus triangles problem” (whether such graphs are vertex-3-colorable). This was solved affirmatively by Fleishner and Stiebitz using the Alon-Tarsi theorem, and later Sachs, inductively.

In the generalization of this question to “cycle plus even $k$-cliques” (I hope it is clear what this means) the answer is that they are all class 1, as you can edge color the edges of the $k$-cliques with $k$-1 colors, and use two remaining colors for the edges of the even cycle in the ($k$+1)-regular graph.