TEDE Coleção:
http://www.bdtd.uerj.br/handle/1/18054
2024-03-29T01:36:12ZAspectos gerais sobre a conformabilidade de grafos
http://www.bdtd.uerj.br/handle/1/20805
Título: Aspectos gerais sobre a conformabilidade de grafos
Autor: Alves Junior, Mauro Nigro
Primeiro orientador: Nobrega, Diana Sasaki
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
Instituição: Universidade do Estado do Rio de Janeiro
Tipo do documento: Tese2023-08-14T00:00:00ZConnected and Disconnected Matchings
http://www.bdtd.uerj.br/handle/1/20424
Título: Connected and Disconnected Matchings
Autor: Masquio, Bruno Porto
Primeiro orientador: Pinto, Paulo Eustáquio Duarte
Abstract: Matching problems in graphs have been studied for a long time, achieving important
results in both theoretical and practical aspects. Over the decades, many variations
of matching problems were studied. Some of them can be solved in polynomial time,
while others can not, unless P = NP. In this thesis, we briefly present the history of
matchings and a survey of some of its variations along with its state of the art. We
also give results on one of these variations: P-matchings. A matching M is a P-
matching if the subgraph induced by the endpoints of the edges of M satisfies property
P. As examples, for appropriate choices of P, the problems Induced Matching,
Uniquely Restricted Matching, Acyclic Matching, Connected Matching
and Disconnected Matching arise. For many of these problems, finding a maximum
P-matching is a knowingly NP-hard problem. Two exceptions, that are the focus of this
thesis, are connected matchings and disconnected matchings, where P is that the graph
is connected and disconnected, respectively. While we can obtain a maximum connected
matching in polynomial time, the complexity of finding a maximum disconnected matching
was still unknown, though asked since 2005 by Goddard, Hedetniemi, Hedetniemi, and
Laskar [Generalized subgraph-restricted matchings in graphs, Discrete Mathematics, 293
(2005) 129 – 138]. In this thesis, we answer this question. In fact, we consider the
generalized problem of finding c-disconnected matchings; such matchings are ones whose
vertex sets induce subgraphs with at least c connected components. We show that, for
every fixed c ≥ 2, this problem is NP-complete even if we restrict the input to bounded
diameter bipartite graphs, while can be solved in polynomial time if c = 1. For the case
when c is part of the input, we show that the problem is NP-complete for chordal graphs
and bounded degree graphs while being solvable in polynomial time for interval graphs.
Then, we explore the parameterized complexity of the problem. We present an FPT
algorithm under the treewidth parameterization, and an XP algorithm for graphs with
a polynomial number of minimal separators when parameterized by c. We complement
these results by showing that, unless NP ⊆ coNP=poly, the related Induced Matching
problem does not admit a polynomial kernel when parameterized by vertex cover and
size of the matching nor when parameterized by vertex deletion distance to clique and
size of the matching. As for connected matchings, we give a linear-time algorithm for
finding a maximum connected matching if a maximum matching is given. So, we turn
our attention to a generalization of connected matchings that considers edge-weighted
graphs and whose problem we name Maximum Weight Connected Matching.
This problem is motivated by the usual Maximum Weight Matching, studied for
decades, and with many applications, including the well-known Assignment problem.
Besides, some other P-matchings, such as acyclic matchings and induced matchings,
were also considered under weighted graphs before. In Maximum Weight Connected
Matching, we want to find a matching M such that the endpoints of its edges induce
a connected subgraph and the sum of the edge weights of M is maximum. Unlike the
unweighted Connected Matching problem, which can be solved in polynomial time for
general graphs, we show that Maximum Weight Connected Matching is NP-hard
even for bounded diameter bipartite graphs, starlike graphs, planar bipartite graphs, and
subcubic planar graphs, while solvable in linear time for trees and graphs having a degree
at most two. When we restrict edge weights to be non-negative only, we show that the
problem turns out to be polynomially solvable for chordal graphs, while it remains NP-hard
for most of the other cases. We also consider the parameterized complexity of Maximum
Weight Connected Matching. On the positive side, we present a single exponential
time algorithm when parameterized by treewidth. As for kernelization, we show that,
even when restricted to binary weights, its decision problem, Weighted Connected
Matching, does not admit a polynomial kernel when parameterized by vertex cover
number under standard complexity-theoretical hypotheses.
Instituição: Universidade do Estado do Rio de Janeiro
Tipo do documento: Tese2022-11-18T00:00:00Z