Search

Abstract: Consider an undirected graph and a subgraph of , on the same vertex set. The -backbone chromatic number is the minimum such that can be properly coloured with colours from , and moreover for each edge of , the colours of its ends differ by at least . In this paper we focus on the case when is planar and is a forest. We give a series of NP-hardness results as well as upper bounds for , depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem. [Copyright &y& Elsevier]

Abstract: A lemma of Fouquet implies that a claw-free graph contains an induced , contains no odd hole, or is quasi-line. In this paper, we use this result to give an improved shortest-odd-hole algorithm for claw-free graphs by exploiting the structural relationship between line graphs and quasi-line graphs suggested by Chudnovsky and Seymour’s structure theorem for quasi-line graphs. Our approach involves reducing the problem to that of finding a shortest odd cycle of length in a graph. Our algorithm runs in time, improving upon Shrem, Stern, and Golumbic’s recent algorithm, which uses a local approach. The best known recognition algorithms for claw-free graphs run in time, or without fast matrix multiplication. [Copyright &y& Elsevier]

Abstract: An -triangulated graph is a graph in which every odd cycle has two non-crossing chords; -triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced -partite subgraph of an -triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is -complete. [Copyright &y& Elsevier]