Kromatski polinomi

undergraduate thesis

• Title (english): Chromatic Polynomials
• Author: Fran Hunski
• Mentor: Mario Krnić (mentor)
• Committee member: Mario Krnić (predsjednik povjerenstva)
• Committee member: Josipa Pina Milišić (član povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom završnom radu bavili smo se kromatskim polinomima. Započeli smo s kratkim povijesnim pregledom kromatskog polinoma i problema četiri boje. Nakon toga smo definirali osnovne tvrdnje i definicije iz teorije grafova poput definicije grafa i kromatskog broja. Sve te definicije i tvrdnje su nam bile potrebne za iskaz tvrdnji i osnovnih svojstava kromatskog polinoma. Prikazali smo opći oblik kromatskog polinoma osnovnih grafova kao što su stablo, ciklus i potpuni graf. Uz osnovne grafove pokazali smo i kromatski polinom nekih dobro poznatih grafova kao što su Heawoodov i Petersenov graf. Na kraju smo prikazali programsku podršku za izračunavanje kromatskih polinoma, neke važne dijelove koda i upute za korištenje aplikacije.

Abstract (english)

In this final BSc thesis paper, we dealt with chromatic polynomials. We started with a brief historical overview of the chromatic polynomial and the four-color problem. After that, we defined basic propositions and definitions from graph theory, such as the definition of a graph and a chromatic number. We needed all these definitions and statements to present the statements and basic properties of the chromatic polynomial. We showed the general form of the chromatic polynomial of basic graphs such as the tree, cycle and complete graph. In addition to the basic graphs, we also showed the chromatic polynomial of some well-known graphs such as the Heawood and Petersen graphs. At the end, we presented software support for calculating chromatic polynomials, some important parts of the code and instructions for using the application.

• Keywords: grafovi; kromatski polinom; bojenje grafa; programska podrška
• Keywords (english): graphs; chromatic polynomial; graph coloring; software support
• Language: croatian
• URN:NBN: urn:nbn:hr:168:361774
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-10-11 09:03:54