The Gyarfas-Sumner conjecture [29, 42] states that for every tree T there is a function f such that for every graph G with no induced subgraph isomorphic to T the chromatic number of G is at most f(o(G)), where o(G) is its clique number. We prove this when T is a tree formed by joining two disjoint paths by an edge.

A class C of graphs has the EH-property if there is a delta > 0 such that every G ∈ C has a clique or stable set of size at least

The strong perfect graph theorem [11] contains a decomposition theorem, and even though perfect graphs can be colored in polynomial time [28], no combinatorial algorithm for this is known. One obstacle for such an algorithm are "skew partitions", which arise from induced subgraphs isomorphic to line graphs. Generalizations of line graphs, so-called orthogonal strip systems, yield particularly bad skew partitions. We prove that in a perfect graph, under mild assumptions, the number of pairwise orthogonal strip systems is bounded by twice the clique number.