5 papers · 1 filter
Majority Edge-Colorings of Graphs
Felix Bock, Rafał Kalinowski, Johannes Pardey +3
We propose the notion of a majority -edge-coloring of a graph , which is an edge-coloring of with colors such that, for every vertex of , at most half the edge…
Relating the independence number and the dissociation number
Felix Bock, Johannes Pardey, Lucia D. Penso +1
The independence number and the dissociation number of a graph are the largest orders of induced subgraphs of of maximum degree at most and at mo…
A bound on the dissociation number
Felix Bock, Johannes Pardey, Lucia D. Penso +1
The dissociation number of a graph is the maximum order of a set of vertices of inducing a subgraph that is of maximum degree at most . Computing the dis…
Relating dissociation, independence, and matchings
Felix Bock, Johannes Pardey, Lucia D. Penso +1
A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most . Computing the dissociation number of a given graph , define…
The matching number of tree and bipartite degree sequences
F. Bock, D. Rautenbach
We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree de…