Search

The Borodin–Kostochka Conjecture states that for a graph G, if Δ (G) ≥ 9 , then χ (G) ≤ max { Δ (G) - 1 , ω (G) } . In this paper, we prove the Borodin–Kostochka Conjecture holding for odd-hole-free graphs. [ABSTRACT FROM AUTHOR]

Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t ≥ 1 , denote by MG t the class of graphs whose maximum multiplicity is at most t. A graph G is called strictly t-degenerate if every non-empty subgraph H of G contains a vertex v whose degree in H is at most t - 1 . The point partition number χ t (G) of G is the smallest number of colors needed to color the vertices of G so that each vertex receives a color and vertices with the same color induce a strictly t-degenerate subgraph of G. So χ 1 is the chromatic number, and χ 2 is known as the point aboricity. The point partition number χ t with t ≥ 1 was introduced by Lick and White (Can J Math 22:1082–1096, 1970). If H is a simple graph, then tH denotes the graph obtained from H by replacing each edge of H by t parallel edges. Then ω t (G) is the largest integer n such that G contains a t K n as a subgraph. Let G be a graph belonging to MG t . Then ω t (G) ≤ χ t (G) and we say that G is χ t -perfect if every induced subgraph H of G satisfies ω t (H) = χ t (H) . Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas (Ann Math 164:51–229, 2006), we give a characterization of χ t -perfect graphs of MG t by a set of forbidden induced subgraphs (see Theorems 2 and 3). We also discuss some complexity problems for the class of χ t -critical graphs. [ABSTRACT FROM AUTHOR]

In this paper, we use the new notion of clique arrangements to suggest that leaf powers are a natural special case of strongly chordal graphs. The clique arrangement $$\mathcal{A}(G)$$ of a chordal graph G is a directed graph that represents the intersections between maximal cliques of G by nodes and the inclusion relation of these vertex subsets by arcs. Recently, strongly chordal graphs have been characterized as the graphs that have a clique arrangement without bad k-cycles for $$k \ge 3$$ . The class $$\mathcal{L}_k$$ of k-leaf powers consists of graphs $$G=(V,E)$$ that have a k-leaf root, that is, a tree T with leaf set V, where $$xy \in E$$ if and only if the T-distance between x and y is at most k. Structural characterizations and linear time recognition algorithms have been found for 2-, 3-, 4-, and, to some extent, 5-leaf powers, and it is known that the union of all k-leaf powers, that is, the graph class $$\mathcal{L}= \bigcup _{k=2}^\infty \mathcal{L}_k$$ , forms a proper subclass of strongly chordal graphs. Despite that, no essential progress has been made lately. In this paper, we characterize the subclass of strongly chordal graphs that have a clique arrangement without certain bad 2-cycles and show that $$\mathcal{L}$$ is contained in that class. [ABSTRACT FROM AUTHOR]

The class of 2K2-free graphs and its various subclasses have been studied in a variety of contexts. In this paper, we are concerned with the colouring of (P3∪P2)-free graphs, a super class of 2K2-free graphs. We derive a O(ω3) upper bound for the chromatic number of (P3∪P2)-free graphs, and sharper bounds for (P3∪P2, diamond)-free graphs and for (2K2, diamond)-free graphs, where ω denotes the clique number. The last two classes are perfect if ω≥5 and ≥4 respectively. [ABSTRACT FROM AUTHOR]