4 papers
Acyclic, Star, and Injective Colouring: Bounding the Diameter
Christoph Brause, Petr Golovach, Barnaby Martin +3
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a for…
Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4
Christoph Brause, Trung Duy Doan, Přemysl Holub +4
For every graph , we consider the class of all connected -free graphs which are distinct from an odd cycle and have independence number at least , and we show…
On forbidden induced subgraphs for K_{1,3}-free perfect graphs
Christoph Brause, Přemysl Holub, Adam Kabela +3
Considering connected -free graphs with independence number at least , Chudnovsky and Seymour (2010) showed that every such graph, say , is -colourable where …
On the extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives
S. Ehard, D. Rautenbach
The famous lower bound on the independence number of a graph due to Caro and Wei is known to be tight if and only if the co…