Results 111 to 120 of about 59,275 (246)
Counterexamples Regarding Linked and Lean Tree‐Decompositions of Infinite Graphs
Journal of Graph Theory, Volume 110, Issue 4, Page 398-407, December 2025.ABSTRACT Kříž and Thomas showed that every (finite or infinite) graph of tree‐width k ∈ N admits a lean tree‐decomposition of width k. We discuss a number of counterexamples demonstrating the limits of possible generalisations of their result to arbitrary infinite tree‐width.
Sandra Albrechtsen +3 more
wiley +1 more source
A short proof of Brooks’ Theorem for vertex arboricity
AKCE International Journal of Graphs and Combinatorics, 2020 The vertex-arboricity of a graph is the minimum number of subsets that the vertices of can be partitioned so that the subgraph induced by each set of vertices is a forest. Kronk and Mitchem proved a generalization of Brooks’ Theorem for vertex arboricity,
Allan Bickle
doaj +1 more source
On Some Algorithmic and Structural Results on Flames
Journal of Graph Theory, Volume 110, Issue 4, Page 392-397, December 2025.ABSTRACT A directed graph F with a root node r is called a flame if for every vertex v other than r the local edge‐connectivity value λ F ( r , v ) from r to v is equal to ϱ F ( v ), the in‐degree of v. It is a classic, simple and beautiful result of Lovász [4] that every digraph D with a root node r has a spanning subgraph F that is a flame and the λ (
Dávid Szeszlér
wiley +1 more source
Forbidden induced subgraphs for line graphs
Discrete Mathematics, 1994 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Lcaron, ubomír Šoltés
openaire +3 more sources
Real models for the framed little n$n$‐disks operads
Journal of Topology, Volume 18, Issue 4, December 2025.Abstract We study the action of the orthogonal group on the little n$n$‐disks operads. As an application we provide small models (over the reals) for the framed little n$n$‐disks operads. It follows in particular that the framed little n$n$‐disks operads are formal (over the reals) for n$n$ even and coformal for all n$n$.
Anton Khoroshkin, Thomas Willwacher
wiley +1 more source
On Sequential Heuristic Methods for the Maximum Independent Set Problem
Discussiones Mathematicae Graph Theory, 2017 We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6] , are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3].
Lê Ngoc C. +2 more
doaj +1 more source
The largest subgraph without a forbidden induced subgraph
20 ...
Fox, Jacob +2 more
openaire +2 more sources
On induced subgraphs of trees, with restricted degrees
Discrete Mathematics, 1994 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Yehuda Roditty +3 more
openaire +2 more sources
Spanning Plane Subgraphs of 1‐Plane Graphs
Journal of Graph Theory, Volume 110, Issue 3, Page 290-297, November 2025.ABSTRACT A graph drawn on the plane is called 1‐plane if each edge is crossed at most once by another edge. In this paper, we show that every 4‐edge‐connected 1‐plane graph has a connected spanning plane subgraph. We also show that there exist infinitely many 4‐connected 1‐plane graphs that have no 2‐connected spanning plane subgraphs.
Kenta Noguchi +2 more
wiley +1 more source