17
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 8
    $\begingroup$ This paper shows that the chromatic number is infinite. $\endgroup$
    – mathworker21
    Commented Apr 8 at 22:21
  • 1
    $\begingroup$ @mathworker21 Thank you. I think that domotorp is right, but that nonetheless your comment should be made into an answer, since its survey of known results is very interesting. $\endgroup$
    – Yaakov Baruch
    Commented Apr 9 at 4:31

1 Answer 1

Reset to default
19
$\begingroup$

This paper shows that the chromatic number is infinite.

Indeed, Theorem 1.1 part (i) with $a=b=c=1$ is what you want.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think this paper also addresses this related Erdos Problem erdosproblems.com/439 $\endgroup$
    – dbal
    Commented Apr 9 at 18:53
  • 1
    $\begingroup$ @dbal See here: mathoverflow.net/a/433095/2480 . I had actually forgotten that I asked the question there, and mathworker21 answered it back then too! $\endgroup$
    – Yaakov Baruch
    Commented Apr 9 at 20:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .