Finding Matching Cuts in H-Free Graphs
F Lucke, D Paulusma, B Ries - Algorithmica, 2023 - Springer
The well-known NP-complete problem Matching Cut is to decide if a graph has a matching
that is also an edge cut of the graph. We prove new complexity results for Matching Cut …
that is also an edge cut of the graph. We prove new complexity results for Matching Cut …
[HTML][HTML] Dichotomies for maximum matching cut: H-freeness, bounded diameter, bounded radius
F Lucke, D Paulusma, B Ries - Theoretical Computer Science, 2024 - Elsevier
Abstract The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect)
matching cut, ie, a (perfect) matching that is also an edge cut of G. Both Matching Cut and …
matching cut, ie, a (perfect) matching that is also an edge cut of G. Both Matching Cut and …
The complexity of the perfect matching‐cut problem
V Bouquet, C Picouleau - Journal of Graph Theory, 2024 - Wiley Online Library
Abstract PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a
perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for …
perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for …
Graphs and digraphs with all 2-factors isomorphic
M Abreu, REL Aldred, M Funk, B Jackson… - Journal of Combinatorial …, 2004 - Elsevier
We show that a digraph which contains a directed 2-factor and has minimum in-degree and
out-degree at least four has two non-isomorphic directed 2-factors. As a corollary, we …
out-degree at least four has two non-isomorphic directed 2-factors. As a corollary, we …
An updated survey on 2-Factors of Regular Graphs
D Labbate, F Romaniello - arXiv preprint arXiv:2408.04642, 2024 - arxiv.org
arXiv:2408.04642v2 [math.CO] 15 Aug 2024 Page 1 An updated survey on 2-Factors of Regular
Graphs Domenico Labbate , Federico Romaniello Dipartimento di Matematica, Informatica ed …
Graphs Domenico Labbate , Federico Romaniello Dipartimento di Matematica, Informatica ed …
Colorings of plane graphs with no rainbow faces
V Jungić, D Král', R Škrekovski - Combinatorica, 2006 - Springer
We prove that each n-vertex plane graph with girth g≥ 4 admits a vertex coloring with at
least⌈ n/2⌉+ 1 colors with no rainbow face, ie, a face in which all vertices receive distinct …
least⌈ n/2⌉+ 1 colors with no rainbow face, ie, a face in which all vertices receive distinct …
A note on the 2-Factor Hamiltonicity Conjecture
M Gorsky, T Johanni, S Wiederrecht - arXiv preprint arXiv:2408.08128, 2024 - arxiv.org
The 2-factor Hamiltonicity Conjecture by Funk, Jackson, Labbate, and Sheehan [JCTB,
2003] asserts that all cubic, bipartite graphs in which all 2-factors are Hamiltonian cycles can …
2003] asserts that all cubic, bipartite graphs in which all 2-factors are Hamiltonian cycles can …
[HTML][HTML] Odd 2-factored snarks
A snark is a cubic cyclically 4-edge connected graph with edge chromatic number four and
girth at least five. We say that a graph G is odd 2-factored if for each 2-factor F of G each …
girth at least five. We say that a graph G is odd 2-factored if for each 2-factor F of G each …
Non‐rainbow colorings of 3‐, 4‐and 5‐connected plane graphs
We study vertex‐colorings of plane graphs that do not contain a rainbow face, ie, a face with
vertices of mutually distinct colors. If G is a 3‐connected plane graph with n vertices, then the …
vertices of mutually distinct colors. If G is a 3‐connected plane graph with n vertices, then the …
Pseudo 2-factor isomorphic regular bipartite graphs
A graph G is pseudo 2-factor isomorphic if the parity of the number of circuits in a 2-factor is
the same for all 2-factors of G. We prove that there exist no pseudo 2-factor isomorphic k …
the same for all 2-factors of G. We prove that there exist no pseudo 2-factor isomorphic k …