Aspectos gerais sobre a conformabilidade de grafos

Abstract

A k-vertex coloring of a graph G = (V,E) is an assignment of k colors to the vertices of G such that adjacent vertices have different colors. The deficiency of G is defined as def(G) = P v∈V (Δ − d(v)), where Δ is the maximum degree of the graph and d(v) is the degree of vertex v. A graph G is conformable if it has a (Δ + 1)-vertex coloring in which the number of color classes (including empty color classes) with a different parity from the parity of |V | is at most def(G). The study of conformable coloring addressed in this thesis was motivated by the rich existing literature and, mainly, by the gaps involving the determination of the computational complexity to decide whether a graph G is conformable. Another motivation lies in the inherent relationships between conformable coloring and the total coloring problem. In this thesis, we classify conformability for several classes of graphs. We determine which balanced colorings are conformable. We prove that if G is regular and Class 1, then L(G) is conformable. Additionally, we demonstrate that every line graph of the complete graph Kn is conformable. Furthermore, we classify the conformability of connected regular bipartite graphs and all subcubic graphs, including the disconnected case. For this purpose, we introduce a new (Δ+1)-vertex coloring called anticonformable coloring, which aids in determining whether a graph is conformable or not. We also define strong conformable coloring, which is the conformable coloring that extends to a (Δ + 1)-total coloring. We present three necessary conditions for a conformable coloring to be strong and show that determining it is NP-complete. We address conformable coloring in the disjoint union of graphs. We show pattern in the disjoint unions between conformable graphs, between anticonformable graphs, and also between conformable and anticonformable graphs. We demonstrate that every k-regular graph with an even k is non-anticonformable. In the case where k is odd, we show that bipartite k-regular graphs are anticonformable. Additionally, we construct a non-anticonformable k-regular graph, denoted by Hk. Finally, we show that the disjoint union between Hk and an odd number of connected components of Kk+1 is non-conformable