Unfriendly partitions of a graph
An unfriendly partition of a graph (V,E) is a partition \(V=V_ 0\cup V_ 1\) such that for every vertex in \(V_ i\), the number of its neighbours in \(V_{1-i}\) is bigger or equal to that of its neighbours in \(V_ i\). The existence of an unfriendly partition of a graph (well-known if the graph is finite) is proved in the case (a) the graph has finitely many vertices of infinite degree only, and in the case (b) there exist infinite cardinals \(m_ 0<m_ 1<...<m_ k\), where \(m_ 1,...,m_ k\) are regular, such that \(| \{x\in V\); d(x) is \(finite\}| <m_ 0\) and \(d(x)\in \{m_ 0,...,m_ k\}\) for every x of infinite degree.
- Partitioning a graph into alliance free sets
- On a graph's security number
- Judicious partitions of graphs
- Structural and algorithmic properties of 2-community structures
- Unfriendly partitions for graphs not containing a subdivison of an infinite cycle
- Note on vertex-partitions of infinite graphs
- Linear time algorithms for weighted offensive and powerful alliances in trees
- Security in graphs
- Majority choosability of digraphs
- Bounds on a graph's security number
- Majority edge-colorings of graphs
- scientific article; zbMATH DE number 4191687 (Why is no real title available?)
- Very cost effective bipartitions in graphs
- Alliances and Related Domination Parameters
- Self-Stabilizing Domination Algorithms
- Problems and results on judicious partitions
- Unfriendly colorings of graphs with finite average degree
- Game $k$-Domination Number of Graphs
- Stabilization Time in Weighted Minority Processes
- Measure-theoretic unfriendly colorings
- Bounds on cost effective domination numbers
- Self-stabilizing algorithms for unfriendly partitions into two disjoint dominating sets
- Every rayless graph has an unfriendly partition
- Every rayless graph has an unfriendly partition
- Generalized graph k-coloring games
- Friendly bisections of random graphs
- Majority choosability of countable graphs
- A note on median eigenvalues of subcubic graphs
- Majority coloring of infinite digraphs
- Partitioning problems via random processes
- Unfriendly partitions when avoiding vertices of finite degree
- Minority sets in graphs
- Median eigenvalues of sparse subcubic graphs
- Majority dominator colorings of graphs
- Mrs. Correct and majority colorings
- Countable graphs are majority 3-choosable
- Unfriendly partition conjecture holds for line graphs
- Majority sets in graphs
- Satisfactory graph partition, variants, and generalizations
This page was built for publication: Unfriendly partitions of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q753841)
