Multiply balanced edge colorings of multigraphs
From MaRDI portal
Abstract: In this paper, a theorem is proved that generalizes several existing amalgamation results in various ways. The main aim is to disentangle a given edge-colored amalgamated graph so that the result is a graph in which the edges are shared out among the vertices in ways that are fair with respect to several notions of balance (such as between pairs of vertices, degrees of vertices in the both graph and in each color class, etc). The connectivity of color classes is also addressed. Most results in the literature on amalgamations focus on the disentangling of amalgamated complete graphs and complete multipartite graphs. Many such results follow as immediate corollaries to the main result in this paper, which addresses amalgamations of graphs in general, allowing for example the final graph to have multiple edges. A new corollary of the main theorem is the settling of the existence of Hamilton decompositions of the family of graphs ; such graphs arose naturally in statistical settings.
Recommendations
- Edge-coloring of multigraphs
- An edge colouring of multigraphs
- scientific article; zbMATH DE number 1874378
- Equipartite edge colouring of multigraphs
- On equitable edge-coloring of multigraphs
- Edge-coloring almost bipartite multigraphs
- On balanced colorings of hypergraphs
- On the $1.1$ Edge-Coloring of Multigraphs
- Balanced coloring of bipartite graphs
- Graphs with multiplicative vertex-coloring 2-edge-weightings
Cites work
- 4-cycle group-divisible designs with two associate classes
- Amalgamations of almost regular edge-colourings of simple graphs
- Amalgamations of connected \(k\)-factorizations.
- Amalgamations of factorizations of complete graphs
- Canonical edge-colourings of locally finite graphs
- Classification and Analysis of Partially Balanced Incomplete Block Designs with Two Associate Classes
- Connected Detachments of Graphs and Generalized Euler Trails
- Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of kkn+1
- Group divisible designs with two associate classes: n=2 or m=2
- Hamilton cycle rich 2-factorizations of complete multipartite graphs
- Hamilton cycle rich two-factorizations of complete graphs
- Hamilton decompositions of complete graphs with a 3-factor leave.
- Hamilton decompositions of complete multipartite graphs with any 2‐factor leave
- Hamiltonian decompositions of complete graphs
- Hamiltonian decompositions of complete regular s-partite graphs
- Highly edge-connected detachments of graphs and digraphs
- scientific article; zbMATH DE number 3491001 (Why is no real title available?)
- scientific article; zbMATH DE number 1792566 (Why is no real title available?)
- scientific article; zbMATH DE number 3353327 (Why is no real title available?)
- Non-separable detachments of graphs
- Nondisconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs
- On A Particular Conference Scheduling Problem
- On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
- The Solution of a Timetabling Problem
Cited in
(19)- Constructing day-balanced round-robin tournaments with partitions
- Fair and internally fair (holey) Hamiltonian decompositions of \(K(n_0, \ldots, n_{p - 1}; \lambda_1, \lambda_2)\)
- More extreme equitable colorings of decompositions of \(K_v\) and \(K_v - F\)
- Maximal sets of Hamilton cycles in complete multipartite graphs. IV
- Fair holey Hamiltonian decompositions of complete multipartite graphs and long cycle frames
- Factorizations of complete multipartite hypergraphs
- Internally fair factorizations and internally fair holey factorizations with prescribed regularity
- Fair 1-factorizations and fair holey 1-factorizations of complete multipartite graphs
- Ryser's theorem for \(\rho\)-Latin rectangles
- Embedding an edge-colored \(K(a^{(p)};\lambda,\mu)\) into a Hamiltonian decomposition of \(K(a^{(p+r)};\lambda,\mu)\)
- Connected Baranyai's theorem
- Extreme equitable block colorings of \(C_4\)-decompositions of \(K_v-F\)
- On evenly-equitable, balanced edge-colorings and related notions
- Amalgamations and equitable block-colorings
- On total chromatic number of complete multipartite graphs
- Total colorings of complete multipartite graphs using amalgamations
- Completing multi-Latin rectangles via factors with prescribed degrees in bipartite graphs
- On total chromatic number of complete multipartite graphs
- Maximal sets of Hamilton cycles in K ( n^r ; _1 , _2)
This page was built for publication: Multiply balanced edge colorings of multigraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897208)
