Kromatski polinomi i njihovi korijeni

Rehlicki, Josipa (2016) Kromatski polinomi i njihovi korijeni. Diploma thesis, Faculty of Science > Department of Mathematics.

[img]
Preview
PDF
Language: Croatian

Download (285kB) | Preview

Abstract

In this thesis we have studied graph coloring. We started with problem that troubled mathematicians for decades, named 4-color problem. We presented this problem mathematically through graphs. After we defined important terms for graph coloring, like chromatic number and chromatic polynomial, we wondered is there any connection between chromatic roots and some known numbers. First, we analyzed Fibonacci numbers and their generalizations, precisely n-anacci constants. After we came to important conclusions, we considered metallic means. Connection of those two sets of number is the golden ratio or golden mean which is 2-anacci constant, also one of metallic means. Parallel with the following proof that applies to 2n-anacci constants, we have shown that the same result is true for all metallic means. Secondly, we defined Beraha numbers. Here we couldn’t generally say something valid for all Beraha’s numbers, but the most important thing is that we can suppose that chromatic roots for plane graph family contain 0,1 and dense subset of (32/27,4). At the last, we mentioned Pisot–Vijayaraghavan numbers. The main characteristic of these numbers is that their conjugates are less than 1 in absolute value, which means they cannot be chromatic roots. At the end of this thesis, we returned to the chromatic intervals. Precisely, we studied nonseparable graphs with k-spanning trees, for k ≤ 3, because for them we can expand the interval which does not contains chromatic roots.

Item Type: Thesis (Diploma thesis)
Supervisor: Došlić, Tomislav
Date: 2016
Number of Pages: 25
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 11 Nov 2016 11:42
Last Modified: 11 Nov 2016 11:42
URI: http://digre.pmf.unizg.hr/id/eprint/5282

Actions (login required)

View Item View Item