Graph representations
Project goals
A graph representation is a correspondence between the vertices of a graph and a family of sets of a given kind such that the information about the sets allows us to retrieve the structure of the graph. The vertices of the extensively investigated interval graphs, for instance, can be represented by intervals on the real line in such a way that two intervals intersect if and only if the corresponding vertices are adjacent. Graph representations have many applications in computer science and operations research, and are an important and well-researched topic nowadays. The objective of this project is to broaden the repertoire of techniques used in the area of graph representations and in combinatorics at large, as well as to solve several specific problems. These problems concern variations of product dimension, double competition number, several versions of intersection representations, and a related graph coloring problem. Some of these problems are the object of my active collaboration with foreigninstitutions, and we already have some partial results regarding them.
Keywords
graphrepresentationsproductdimensionintersectionrepresentationdoublecompetitionnumber
Public support
Provider
Czech Science Foundation
Programme
Post-graduate (doctorate) grants
Call for proposals
Postdoktorandské granty 12 (SGA02012GA1PD)
Main participants
—
Contest type
VS - Public tender
Contract ID
P201-12-P288
Alternative language
Project name in Czech
Reprezentace grafů
Annotation in Czech
Reprezentací grafu nazýváme přiřazení objektů z dané množiny vrcholům grafu takovým způsobem, že z informace o přiřazených objektech je možno zpětně získat strukturu původního grafu. Vrcholům populárních intervalových grafů například můžeme přiřadit intervaly na přímce tak, že hrany grafu odpovídají přesně dvojicím protínajících se intervalů. Reprezentace grafů mají mnoho použití v informatice a operačním výzkumu, a v dnešní době je to důležitá a velmi zkoumaná oblast teorie grafů. Cílem tohoto projektuje vývoj metod použitelných v teorii grafových reprezentací a celkově v kombinatorice, jakožto i řešení několika konkrétních problémů. Tyto problémy se týkají variant produktové dimenze a dvojitého konkurenčního čísla, různých druhů průnikových reprezentací, a příbuzných otázek o barvení grafu. Na některých z těchto problémů aktivně spolupracuji se zahraničními institucemi, a máme již částečné výsledky.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
Although the investigator significantly diverged from the original goals specified in the project proposal, the results obtained within the project constitute a valuable contribution to interesting questions related to graph representations, and they areconsistent with the project objectives. Outputs of the project are 2 papers in high quality international journals and 1 book chapter.
Solution timeline
Realization period - beginning
Jan 1, 2012
Realization period - end
Dec 31, 2015
Project status
U - Finished project
Latest support payment
Apr 10, 2015
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP16-GA0-GP-U/01:1
Data delivery date
May 6, 2016
Finance
Total approved costs
1,309 thou. CZK
Public financial support
1,309 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
1 309 CZK thou.
Public support
1 309 CZK thou.
0%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2012 - 31. 12. 2015