Zobrazeno 1 - 10
of 317
pro vyhledávání: '"Figueiredo, Celina"'
For a property $\mathcal{P}$ of graphs, the $\mathcal{P}$-\textsc{Sandwich-Problem}, introduced by Golumbic and Shamir (1993), is the following: Given a pair of graphs $(G_1, G_2)$ on the same vertex set $V$, does there exist a graph $G$ such that $V
Externí odkaz:
http://arxiv.org/abs/2404.10888
A total coloring of a graph colors all its elements, vertices and edges, with no adjacency conflicts. The Total Coloring Conjecture (TCC) is a sixty year old challenge, says that every graph admits a total coloring with at most maximum degree plus tw
Externí odkaz:
http://arxiv.org/abs/2403.16310
Graph pebbling is a game played on graphs with pebbles on their vertices. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex. The pebbling number $\pi(G)$ is the smallest $t$ so that from any initial confi
Externí odkaz:
http://arxiv.org/abs/2303.13292
In this paper, we prove that the MaxCut problem is NP-complete on permutation graphs, settling a long-standing open problem that appeared in the 1985 column of the "Ongoing Guide to NP-completeness" by David S. Johnson.
Externí odkaz:
http://arxiv.org/abs/2202.13955
Autor:
Castonguay, Diane, de Figueiredo, Celina M. H., Kowada, Luis Antonio, Patrão, Caroline Reis, Sasaki, Diana
A \textit{$k$-total coloring} of a graph $G$ is an assignment of $k$ colors to its elements (vertices and edges) so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer $k$ for which the graph $
Externí odkaz:
http://arxiv.org/abs/2110.14453
What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 "Graph Restrictions and Their Effect" of D. S. Johnson's Ongoing guide, where several puzzles were proposed in a summ
Externí odkaz:
http://arxiv.org/abs/2104.14395
The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson on his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by
Externí odkaz:
http://arxiv.org/abs/2012.09804
Autor:
Abreu, Alexandre, Cunha, Luís, de Figueiredo, Celina, Marquezino, Franklin, Posner, Daniel, Portugal, Renato
We propose the total staggered quantum walk model and the total tessellation cover of a graph. This model uses the concept of total tessellation cover to describe the motion of the walker who is allowed to hop both to vertices and edges of the graph,
Externí odkaz:
http://arxiv.org/abs/2002.08992
Autor:
Abreu, Alexandre, Cunha, Luís, de Figueiredo, Celina, Kowada, Luis, Marquezino, Franklin, Portugal, Renato, Posner, Daniel
A tessellation of a graph is a partition of its vertices into vertex disjoint cliques. A tessellation cover of a graph is a set of tessellations that covers all of its edges, and the tessellation cover number, denoted by $T(G)$, is the size of a smal
Externí odkaz:
http://arxiv.org/abs/1908.10844
Publikováno v:
In Procedia Computer Science 2023 223:35-42
