Skip to main content
Became Hot Network Question
edited tags
Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43
added 4 characters in body; edited title
Source Link
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Can the Pythagorean Graph be finitely colored?

Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, proving that the chromatic number $\chi$ is $>3$. Is anything more known about this problem? Could $\chi$ even be infinite?

Pythagorean subgraph

The numbers in the example are as follows: $17089712640 - 555284201472, 357569372160 - 555284201472, 65554384896 - 555284201472, 1098884475 - 2865239520, 1098884475 - 4215208140, 2865239520 - 4215208140, 2865239520 - 5954748800, 5954748800 - 17089712640, 1098884475 - 35705292480, 4215208140 - 35705292480, 17089712640 - 37193013000, 2865239520 - 37193013000, 5954748800 - 37193013000, 17089712640 - 65554384896, 65554384896 - 357569372160, 35705292480 - 3016991577600, 357569372160 - 3028822917120, 3016991577600 - 4685210449920, 3028822917120 - 9610688102400, 4685210449920 - 9610688102400, 3028822917120 - 11618254061568, 357569372160 - 11618254061568, 9610688102400 - 11618254061568, 3016991577600 - 25555693363200, 4685210449920 - 25555693363200, 9610688102400 - 25555693363200$

17089712640 - 555284201472, 357569372160 - 555284201472, 65554384896 - 555284201472, 1098884475 - 2865239520, 1098884475 - 4215208140, 2865239520 - 4215208140, 2865239520 - 5954748800, 5954748800 - 17089712640, 1098884475 - 35705292480, 4215208140 - 35705292480, 17089712640 - 37193013000, 2865239520 - 37193013000, 5954748800 - 37193013000, 17089712640 - 65554384896, 65554384896 - 357569372160, 35705292480 - 3016991577600, 357569372160 - 3028822917120, 3016991577600 - 4685210449920, 3028822917120 - 9610688102400, 4685210449920 - 9610688102400, 3028822917120 - 11618254061568, 357569372160 - 11618254061568, 9610688102400 - 11618254061568, 3016991577600 - 25555693363200, 4685210449920 - 25555693363200, 9610688102400 - 25555693363200

Can the Pythagorean Graph be colored?

Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, proving that the chromatic number $\chi$ is $>3$. Is anything more known about this problem? Could $\chi$ even be infinite?

Pythagorean subgraph

The numbers in the example are as follows: $17089712640 - 555284201472, 357569372160 - 555284201472, 65554384896 - 555284201472, 1098884475 - 2865239520, 1098884475 - 4215208140, 2865239520 - 4215208140, 2865239520 - 5954748800, 5954748800 - 17089712640, 1098884475 - 35705292480, 4215208140 - 35705292480, 17089712640 - 37193013000, 2865239520 - 37193013000, 5954748800 - 37193013000, 17089712640 - 65554384896, 65554384896 - 357569372160, 35705292480 - 3016991577600, 357569372160 - 3028822917120, 3016991577600 - 4685210449920, 3028822917120 - 9610688102400, 4685210449920 - 9610688102400, 3028822917120 - 11618254061568, 357569372160 - 11618254061568, 9610688102400 - 11618254061568, 3016991577600 - 25555693363200, 4685210449920 - 25555693363200, 9610688102400 - 25555693363200$

Can the Pythagorean Graph be finitely colored?

Define the Pythagorean Graph as having nodes $a,b\in \mathbb{N}_{\ge 3}$ and an edge $a\rightarrow b$ if and only if $a^2+b^2$ is a square. After much searching I found the example in the picture, proving that the chromatic number $\chi$ is $>3$. Is anything more known about this problem? Could $\chi$ even be infinite?

Pythagorean subgraph

The numbers in the example are as follows:

17089712640 - 555284201472, 357569372160 - 555284201472, 65554384896 - 555284201472, 1098884475 - 2865239520, 1098884475 - 4215208140, 2865239520 - 4215208140, 2865239520 - 5954748800, 5954748800 - 17089712640, 1098884475 - 35705292480, 4215208140 - 35705292480, 17089712640 - 37193013000, 2865239520 - 37193013000, 5954748800 - 37193013000, 17089712640 - 65554384896, 65554384896 - 357569372160, 35705292480 - 3016991577600, 357569372160 - 3028822917120, 3016991577600 - 4685210449920, 3028822917120 - 9610688102400, 4685210449920 - 9610688102400, 3028822917120 - 11618254061568, 357569372160 - 11618254061568, 9610688102400 - 11618254061568, 3016991577600 - 25555693363200, 4685210449920 - 25555693363200, 9610688102400 - 25555693363200

edited tags
Link
GH from MO
  • 105.4k
  • 8
  • 293
  • 398
edited title
Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43
Loading
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43
Loading