Search

The b-chromatic number of a graph G , χ b ( G ) , is the largest integer k such that G has a k -vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b- Chromatic Number problem, the objective is to decide whether χ b ( G ) ≥ k . Testing whether χ b ( G ) = Δ ( G ) + 1 , where Δ ( G ) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvíl, Tuza and Voigt, WG 2002). We show that b- Chromatic Number is W[1]-hard when parameterized by k , resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k = Δ ( G ) + 1 , we design an algorithm for b- Chromatic Number running in time 2 O ( k 2 log ⁡ k ) n O ( 1 ) . Finally, we show that b- Chromatic Number for an n -vertex graph can be solved in time O ( 3 n n 4 log ⁡ n ) . [ABSTRACT FROM AUTHOR]

Abstract: We define strong λ-extendibility as a variant of the notion of λ-extendible properties of graphs (Poljak and Turzík, Discrete Mathematics, 1986). We show that the parameterized APT(Π) problem — given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that and H has at least edges — is fixed-parameter tractable (FPT) for all , for all strongly λ-extendible graph properties Π for which the APT(Π) problem is FPT on graphs which are vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards–Erdős bound, and yield FPT algorithms for several graph problems parameterized above lower bounds. [Copyright &y& Elsevier]

Given a graph G and a parameter k ∈ N , the parameterized K 4 - minor cover problem asks whether at most k vertices can be deleted to turn G into a K 4 -minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set , which can also be expressed as Treewidth - t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set . While single-exponential FPT algorithms, i.e. running in 2 O ( k ) ⋅ n O ( 1 ) time, are known for these two latter problems, it was open whether the K 4 - minor cover problem could be solved in single-exponential FPT time. This paper answers this question in the affirmative. Observe that it is known to be unlikely that Treewidth - t Vertex Deletion can be solved in time 2 o ( k ) ⋅ n O ( 1 ) . [ABSTRACT FROM AUTHOR]

In the Undirected Eulerian Edge Deletion problem, we are given an undirected graph and an integer k , and the objective is to delete k edges such that the resultant graph is a connected graph in which all the vertices have even degrees. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion . In this paper, using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2 O ( k ) n O ( 1 ) , improving the algorithms by Cygan et al. [Algorithmica, 2014] and affirmatively answer the open problem posed by them. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. [ABSTRACT FROM AUTHOR]