Fraternal augmentations of graphs, coloration and minors

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004925" target="_blank" >RIV/00216208:11320/07:00004925 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Fraternal augmentations of graphs, coloration and minors
Original language description
We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and homomorphism dualities.
Czech name
Bratrská zvětšení grafů, obarvení a minory
Czech description
Zavádíme třídy grafů s omezenou expanzí jakožto zobecnění vlastních minorově uzavřených tříd a tříd grafů s omezenými stupni. Zobecníme na tyto třídy výsledky známé pro minorově uzavřené třídy a pro grafy s omezenými stupni, například existenci obarvenínízké stromové šířky, lineární algoritmus na testování podgrafového homomorfismu pro pevný vzor a homomorfismové duality.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)