All Outputs (4)

On-line coloring of H-free bipartite graphs. (2006)
Presentation / Conference Contribution
Broersma, H. J., Capponi, A., & Paulusma, D. (2006, May). On-line coloring of H-free bipartite graphs. Presented at 6th Italian Conference on Algorithms and Complexity (CIAC 2006)., Rome, Italy

We present a new on-line algorithm for coloring bipartite graphs. This yields a new upper bound on the on-line chromatic number of bipartite graphs, improving a bound due to Lovász, Saks and Trotter. The algorithm is on-line competitive on various cl... Read More about On-line coloring of H-free bipartite graphs..

Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult (2006)
Journal Article
Broersma, H., Fomin, F., Kratochvil, J., & Woeginger, G. (2006). Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult. Algorithmica, 44(4), 343-361. https://doi.org/10.1007/s00453-005-1176-8

We consider the problem of coloring a planar graph with the minimum number of colors so that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem. We present a... Read More about Planar graph coloring avoiding monochromatic subgraphs : trees and paths make it difficult.

Global connectivity and expansion : long cycles and factors in f-connected graphs (2006)
Journal Article
Brandt, S., Broersma, H., Diestel, R., & Kriesell, M. (2006). Global connectivity and expansion : long cycles and factors in f-connected graphs. Combinatorica, 26(1), 17-36. https://doi.org/10.1007/s00493-006-0002-5

Given a function f : N → R, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k ≤ (n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expan... Read More about Global connectivity and expansion : long cycles and factors in f-connected graphs.

The computational complexity of the parallel knock-out problem (2006)
Presentation / Conference Contribution
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006, March). The computational complexity of the parallel knock-out problem. Presented at 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.