Výsledky vyhledávání - "Subi, Carlos"

Report

On finding hamiltonian cycles in Barnette graphs

Autor: Gh., Behrooz Bagheri, Feder, Tomas, Fleischner, Herbert, Subi, Carlos

Publikováno v: Fundamenta Informaticae, Volume 188, Issue 1 (December 15, 2022) fi:10437

In this paper, we deal with hamiltonicity in planar cubic graphs G having a facial 2-factor Q via (quasi) spanning trees of faces in G/Q and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if B

Externí odkaz: http://arxiv.org/abs/2212.02668

Zobrazit plný text záznamu

Report

Complexity of acyclic colorings of graphs and digraphs with degree and girth constraints

Autor: Feder, Tom\' as, Hell, Pavol, Subi, Carlos

We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic number of a digraph, and the arboricity of a graph.) For any girth and suff

Externí odkaz: http://arxiv.org/abs/1907.00061

Zobrazit plný text záznamu

Report

Distance-Two Colorings of Barnette Graphs

Autor: Feder, Tomas, Hell, Pavol, Subi, Carlos

Barnette identified two interesting classes of cubic polyhedral graphs for which he conjectured the existence of a Hamiltonian cycle. Goodey proved the conjecture for the intersection of the two classes. We examine these classes from the point of vie

Externí odkaz: http://arxiv.org/abs/1807.01410

Zobrazit plný text záznamu

Report

On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs

Autor: Gh., Behrooz Bagheri, Feder, Tomas, Fleischner, Herbert, Subi, Carlos

It is a well-known fact that hamiltonicity in planar cubic graphs is an NP-complete problem. This implies that the existence of an A-trail in plane eulerian graphs is also an NP-complete problem even if restricted to planar 3-connected eulerian graph

Externí odkaz: http://arxiv.org/abs/1806.06713

Zobrazit plný text záznamu

Report

Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette's Conjecture

Autor: Gh., Behrooz Bagheri, Feder, Tomas, Fleischner, Herbert, Subi, Carlos

We study the existence of hamiltonian cycles in plane cubic graphs G having a facial 2-factor Q. Thus hamiltonicity in G is transformed into the existence of a (quasi) spanning tree of faces in the contraction G/Q. In particular, we study the case wh

Externí odkaz: http://arxiv.org/abs/1806.05483

Zobrazit plný text záznamu