(Sub)Fall coloring of graphs

Abstract

Given a graph G, a (proper) k-coloring of G is a function f : V(G) → {1,..., k} such that f(u) ̸= f(v), for every edge uv ∈ E(G). Given a k-coloring f of a graph G, a vertex u ∈ V(G) is a b-vertex with respect to f if for every color i ∈ {1,..., k} − { f(u)} there exists at least one vertex v ∈ V(G) such that f(v) = i and uv ∈ E(G). A k-coloring f of a graph G is a fall k-coloring if every vertex u ∈ V(G) is a b-vertex with respect to f ; If a graph G admits a fall k-coloring for some k, the fall achromatic number, denoted by ψf(G), is the maximum positive integer k such that G admits a fall k-coloring. Given a graph G and a positive integer k, a subfall k-coloring of G is a fall k-coloring of some induced subgraph H ⊆ G; and the subfall achromatic number, denoted by ψf s(G), is the maximum positive integer k such that G admits a subfall k-coloring. In this preliminary work, we present a brief review of the results about fall k-coloring found in the literature which are the closest related to the subfall coloring. Furthermore, we prove that deciding whether a graph G admits a subfall k-coloring is an NP-complete problem for every integer k ≥ 4, answering a question raised in (Dunbar et al., 2000). We also give a dynamic programming algorithm to decide whether a graph G admits a subfall k-coloring when parameterized by its treewidth tw(G) in FPT time, when k ≥ 3. In addition, given a graph G, we establish the continuity of the parameter ψf s(G) and its relations with some parameters, which are the b-chromatic number b(G) and the Grundy number Γ(G). Finally, we define the subfall achromatic index of a graph G as the corresponding parameter for edge coloring and prove a Vizing-like theorem for it on planar and outerplanar graphs.