Skip to main content
MathOverflow

Return to Answer

added 400 characters in body
Source Link
patrick labarque
patrick labarque
  • 1
  • 3

The stronger generalization from the comment above.

  • Assign a trianglenumber of $+1$ or $-1$ to each triangle of a maximal planar graph with $v$ vertices and make all $2^{2(v-2)}$ different variations.

  • For every variation define the vertexnumbers by making the sum $\mod 3$ of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of $0$, $1$ or $2$.

Conjecture 1: The number of different variations of vertexnumbers for $v-2$ vertices is equal to $3^{v-2}$ if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this $v-2$ vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then $4$-colorable.

The number of different variations of vertexnumbers for ALL vertices is more than $3^{v-2}$ except if all vertices have even degree (the graph is then 3-vertex-colorable).

Conjecture 2: The number of different variations of vertexnumbers for $v$ vertices is equal to $3^{v-2}$ if all vertices have even degree.

Understanding conjecture 2 can help to better understand conjecture 1.

The stronger generalization from the comment above.

  • Assign a trianglenumber of $+1$ or $-1$ to each triangle of a maximal planar graph with $v$ vertices and make all $2^{2(v-2)}$ different variations.

  • For every variation define the vertexnumbers by making the sum $\mod 3$ of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of $0$, $1$ or $2$.

Conjecture: The number of different variations of vertexnumbers for $v-2$ vertices is equal to $3^{v-2}$ if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this $v-2$ vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then $4$-colorable.

The stronger generalization from the comment above.

  • Assign a trianglenumber of $+1$ or $-1$ to each triangle of a maximal planar graph with $v$ vertices and make all $2^{2(v-2)}$ different variations.

  • For every variation define the vertexnumbers by making the sum $\mod 3$ of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of $0$, $1$ or $2$.

Conjecture 1: The number of different variations of vertexnumbers for $v-2$ vertices is equal to $3^{v-2}$ if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this $v-2$ vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then $4$-colorable.

The number of different variations of vertexnumbers for ALL vertices is more than $3^{v-2}$ except if all vertices have even degree (the graph is then 3-vertex-colorable).

Conjecture 2: The number of different variations of vertexnumbers for $v$ vertices is equal to $3^{v-2}$ if all vertices have even degree.

Understanding conjecture 2 can help to better understand conjecture 1.

LaTeX formatting
Source Link
David Roberts ♦
David Roberts ♦
  • 35.5k
  • 11
  • 124
  • 349

The stronger generalization from the comment above.

  • Assign a trianglenumber of +1$+1$ or -1$-1$ to each triangle of a maximal planar graph with v$v$ vertices and make all 2^(2*(v-2))$2^{2(v-2)}$ different variations.

  • For every variation define the vertexnumbers by making the sum mod3$\mod 3$ of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of 0$0$, 1$1$ or 2$2$.

Conjecture: The number of different variations of vertexnumbers for v-2$v-2$ vertices is equal to 3^(v-2)$3^{v-2}$ if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this v-2$v-2$ vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then 4$4$-colorable.

The stronger generalization from the comment above.

  • Assign a trianglenumber of +1 or -1 to each triangle of a maximal planar graph with v vertices and make all 2^(2*(v-2)) different variations.

  • For every variation define the vertexnumbers by making the sum mod3 of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of 0, 1 or 2.

Conjecture: The number of different variations of vertexnumbers for v-2 vertices is equal to 3^(v-2) if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this v-2 vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then 4-colorable.

The stronger generalization from the comment above.

  • Assign a trianglenumber of $+1$ or $-1$ to each triangle of a maximal planar graph with $v$ vertices and make all $2^{2(v-2)}$ different variations.

  • For every variation define the vertexnumbers by making the sum $\mod 3$ of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of $0$, $1$ or $2$.

Conjecture: The number of different variations of vertexnumbers for $v-2$ vertices is equal to $3^{v-2}$ if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this $v-2$ vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then $4$-colorable.

edited body
Source Link
patrick labarque
patrick labarque
  • 1
  • 3

The stronger generalization from the comment belowabove.

  • Assign a trianglenumber of +1 or -1 to each triangle of a maximal planar graph with v vertices and make all 2^(2*(v-2)) different variations.

  • For every variation define the vertexnumbers by making the sum mod3 of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of 0, 1 or 2.

Conjecture: The number of different variations of vertexnumbers for v-2 vertices is equal to 3^(v-2) if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this v-2 vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then 4-colorable.

The stronger generalization from the comment below.

  • Assign a trianglenumber of +1 or -1 to each triangle of a maximal planar graph with v vertices and make all 2^(2*(v-2)) different variations.

  • For every variation define the vertexnumbers by making the sum mod3 of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of 0, 1 or 2.

Conjecture: The number of different variations of vertexnumbers for v-2 vertices is equal to 3^(v-2) if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this v-2 vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then 4-colorable.

The stronger generalization from the comment above.

  • Assign a trianglenumber of +1 or -1 to each triangle of a maximal planar graph with v vertices and make all 2^(2*(v-2)) different variations.

  • For every variation define the vertexnumbers by making the sum mod3 of the trianglenumbers for all the triangles incident to each vertex. The vertices have now a vertexnumber of 0, 1 or 2.

Conjecture: The number of different variations of vertexnumbers for v-2 vertices is equal to 3^(v-2) if the two missing vertices are adjacent.

Corollary: Then there is also a proper vertexnumbering (all vertexnumbers=0) for this v-2 vertices. It is easy to prove then that the two missing vertices have also a vertexnumber=0. The maximal planar graph is then 4-colorable.

edited body
Source Link
patrick labarque
patrick labarque
  • 1
  • 3
Source Link
patrick labarque
patrick labarque
  • 1
  • 3
Post Made Community Wiki by patrick labarque