Structural properties of graph classes characterized by forbidden subgraphs
Project goals
Many important graph properties can be characterized in terms of forbidden induced subgraphs, or become more tractable when considered in such graph classes. The problems considered in such classes under this project belong to Hamiltonian and to chromatic graph theory. In Hamiltonian graph theory, we focus on Hamiltonian properties of line graphs and their generalizations (Thomassen’s and Matthews-Sumner’s conjectures and related problems), and on forbidden subgraphs guaranteeing Hamilton-type properties. In this part of the project, development of corresponding methods, namely, local graph operations (closure techniques), is an important part. In chromatic graph theory, we will consider especially chromatic properties of graphs from classes defined by forbidden induced subgraphs.
Keywords
graphhamiltonian graphline graphThomassen’s conjectureclosureforbidden subgraphgraph coloringcubic graph
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202000001
Main participants
Západočeská univerzita v Plzni / Fakulta aplikovaných věd
Contest type
VS - Public tender
Contract ID
20-09525S
Alternative language
Project name in Czech
Strukturální vlastnosti tříd grafů charakterizovaných zakázanými podgrafy
Annotation in Czech
Mnoho důležitých grafových vlastností je možno charakterizovat pomocí zakázaných indukovaných podgrafů, nebo se jejich studium stává v takových třídách grafů zvládnutelnějším. Problémy, zkoumané v takových třídách v rámci tohoto projektu, spadají do hamiltonovské a chromatické teorie grafů. V hamiltonovské teorii grafů se zaměříme především na hamiltonovské vlastnosti hranových grafů a jejich zobecnění (Thomassenova a Matthews-Sumnerova hypotéza a související problémy), a na zakázané podgrafy garantující vlastnosti hamiltonovského typu. Mezi důležité metody, jejichž rozvoj je součástí projektu, zde patří především grafové operace lokálního charakteru (uzávěrové techniky). V chromatické teorii grafů budeme analogicky zkoumat především chromatické vlastnosti grafů z tříd, definovaných pomocí zakázaných indukovaných podgrafů.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project met most of its goals and resulted in a very satisfactory number of publications in good graph theory journals. The project lacks a bit publications in top-shelf venues (one JCTB publication) and therefore its significance and impact may be limited.
Solution timeline
Realization period - beginning
Jan 1, 2020
Realization period - end
Jun 30, 2023
Project status
U - Finished project
Latest support payment
Apr 1, 2023
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
CEP24-GA0-GA-U
Data delivery date
May 21, 2024
Finance
Total approved costs
7,905 thou. CZK
Public financial support
7,644 thou. CZK
Other public sources
261 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
7 905 CZK thou.
Public support
7 644 CZK thou.
96%
Provider
Czech Science Foundation
OECD FORD
Pure mathematics
Solution period
01. 01. 2020 - 30. 06. 2023