http://www.tu-ilmenau.de

Logo TU Ilmenau


Arbeitsgruppe
Diskrete Mathematik und Algebra


Foto des Ansprechpartners
Ansprechpartner

Univ.-Prof. Dr. rer. nat. habil. Matthias Kriesell

Fachgebietsleiter

Telefon +49 3677 69-3633

E-Mail senden


Ihre Position

INHALTE

Publikationsliste seit 1990

Anzahl der Treffer: 364
Erstellt: Wed, 13 Dec 2017 23:04:26 +0100 in 0.0275 sec


Harant, Jochen; Jendrol', Stanislav
Nonrepetitive vertex colorings of graphs. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 312 (2012), 2, S. 374-380
http://dx.doi.org/10.1016/j.disc.2011.09.027
Stiebitz, Michael; Scheide, Diego; Toft, Bjarne; Favrholdt, Lene M.
Graph edge coloring : Vizing's theorem and Goldberg's conjecture. - Hoboken, NJ : Wiley. - XIV, 321 S.. - (Wiley series in discrete mathematics and optimization)
ISBN 111809137X = 978-1-118-09137-1
"Written by world authorities on graph theory, this book features many new advances and applications in graph edge coloring, describes how the results are interconnected, and provides historial context throughout. Chapter coverage includes an introduction to coloring preliminaries and lower and upper bounds; the Vizing fan; the Kierstead path; simple graphs and line graphs of multigraphs; the Tashkinov tree; Goldberg's conjecture; extreme graphs; generalized edge coloring; and open problems. It serves as a reference for researchers interested in discrete mathematics, graph theory, operations research, theoretical computer science, and combinatorial optimization, as well as a graduate-level course book for students of mathematics, optimization, and computer science"-- Provided by publisher

"This book provides an overview of this development as well as describes how the many different results are related"--


http://www.gbv.de/dms/ilmenau/toc/670551414.PDF
Böhme, Thomas; Schreyer, Jens; Škrabul'áková, Erika
A note on semi-steady states in stochastic cellular automata. - In: Autonomous systems: developments and trends / Workshop on Autonomous Systems (Mallorca) : 2011.. : . - Berlin [u.a.] : Springer, ISBN 978-3-642-24805-4, (2011), S. 313-323

Löwenstein, Christian; Rautenbach, Dieter
Cohabitation of independent sets and dominating sets in trees. - In: Utilitas mathematicaUtilitas mathematica : an international journal of discrete and combinatorial mathematics. - Durban : Department of Mathematics and Applied Mathematics, Univ. of KwaZulu-Natal : an international journal of discrete and combinatorial mathematics. - Durban : Department of Mathematics and Applied Mathematics, Univ. of KwaZulu-Natal, ISSN 03153681, Bd. 85 (2011), S. 299-308
Harant, Jochen; Jendrol, Stanislav; Madaras, Tomáš
Upper bounds on the sum of powers of the degrees of a simple planar graph. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 67 (2011), 2, S. 112-123
http://dx.doi.org/10.1002/jgt.20519
Böhme, Thomas; Kostochka, Alexander; Thomason, Andrew
Minors in graphs with high chromatic number. - In: Combinatorics, probability & computing : CPC. - Cambridge : Cambridge Univ. Press, ISSN 14692163, Bd. 20 (2011), 4, S. 513-518
http://dx.doi.org/10.1017/S0963548311000174
Harant, Jochen
A lower bound on independence in terms of degrees. - In: Discrete applied mathematics. - [S.l.] : Elsevier, Bd. 159 (2011), 10, S. 966-970
http://dx.doi.org/10.1016/j.dam.2011.03.003
Kostochka, Alexandr V.; Stiebitz, Michael; Woodall, Douglas R.
Ohba's conjecture for graphs with independence number five. - In: Discrete mathematics. - Amsterdam [u.a.] : Elsevier, Bd. 311 (2011), 12, S. 996-1005
http://dx.doi.org/10.1016/j.disc.2011.02.026
Löwenstein, Christian; Pedersen, Anders Sune; Rautenbach, Dieter; Regen, Friedrich
Independence, odd girth, and average degree. - In: Journal of graph theory. - New York, NY [u.a.] : Wiley, ISSN 10970118, Bd. 67 (2011), 2, S. 96-111
http://dx.doi.org/10.1002/jgt.20518
Regen, Friedrich
On cycles and independence in graphs. - Online-Ressource (PDF-Datei: 84 S., 1166 KB)
Ilmenau : Techn. Univ., Diss., 2010

Das erste Fachkapitel ist der Berechnung von Kreispackungszahlen, d.h. der maximalen Größe kanten- bzw. eckendisjunkter Kreispackungen, gewidmet. Da diese Probleme bekanntermaßen sogar für subkubische Graphen schwer sind, behandelt der erste Abschnitt die Komplexität des Packens von Kreisen einer festen Länge l in Graphen mit Maximalgrad Delta. Dieses für l=3 von Caprara und Rizzi gelöste Problem wird hier auf alle größeren Kreislängen l verallgemeinert. Der zweite Abschnitt beschreibt die Struktur von Graphen, für die die Kreispackungszahlen einen vorgegebenen Abstand zur zyklomatischen Zahl haben. Die 2-zusammenhängenden Graphen mit dieser Eigenschaft können jeweils durch Anwendung einer einfachen Erweiterungsregel auf eine endliche Menge von Graphen erzeugt werden. Aus diesem Strukturergebnis wird ein fpt-Algorithmus abgeleitet. Das zweite Fachkapitel handelt von der Größenordnung der minimalen Anzahl von Kreislängen in einem Hamiltongraph mit q Sehnen. Eine Familie von Beispielen zeigt, dass diese Unterschranke höchstens die Wurzel von q+1 ist. Dem Hauptsatz dieses Kapitels zufolge ist die Zahl der Kreislängen eines beliebigen Hamiltongraphen mit q Sehnen mindestens die Wurzel von 4/7*q. Der Beweis beruht auf einem Lemma von Faudree et al., demzufolge der Graph, der aus einem Weg mit Endecken x und y und q gleichlangen Sehnen besteht, x-y-Wege von mindestens q/3 verschiedenen Längen enthält. Der erste Abschnitt enthält eine Korrektur des ursprünglich fehlerhaften Beweises und zusätzliche Schranken. Der zweite Abschnitt leitet daraus die Unterschranke für die Anzahl der Kreislängen ab. Das letzte Fachkapitel behandelt Unterschranken für den Unabhängigkeitsquotienten, d.h. den Quotienten aus Unabhängigkeitszahl und Ordnung eines Graphen, für Graphen gegebener Dichte. In der Einleitung werden bestmögliche Schranken für die Klasse aller Graphen sowie für große zusammenhängende Graphen aus bekannten Ergebnissen abgeleitet. Danach wird die Untersuchung auf durch das Verbot kleiner ungerader Kreise eingeschränkte Graphenklassen ausgeweitet. Das Hauptergebnis des ersten Abschnitts ist eine Verallgemeinerung eines Ergebnisses von Heckman und Thomas, das die bestmögliche Schranke für zusammenhängende dreiecksfreie Graphen mit Durchschnittsgrad bis zu 10/3 impliziert und die extremalen Graphen charakterisiert. Der Rest der ersten beiden Abschnitte enthält Vermutungen ähnlichen Typs für zusammenhängende dreiecksfreie Graphen mit Durchschnittsgrad im Intervall [10/3, 54/13] und für zusammenhängende Graphen mit ungerader Taillenweite 7 mit Durchschnittsgrad bis zu 14/5. Der letzte Abschnitt enthält analoge Beobachtungen zum Bipartitionsquotienten. Die Arbeit schließt mit Vermutungen zu Unterschranken und die zugehörigen Klassen extremaler Graphen für den Bipartitionsquotienten.


http://www.db-thueringen.de/servlets/DocumentServlet?id=18161