4
votes
Accepted
Complexity of maximum k-edge-colorable subgraph of a bipartite graph
A bipartite multigraph is $k$-edge colorable iff the maximum degree of any vertex is at most $k$. So we are asking for a subgraph $H=(V,F)$ of a given bipartite graph $G=(V,E)$ such that $\delta_H(v) \...
- 6,979
2
votes
Accepted
Balanced set coloring
I think this question is closely related to the term discrepancy.
Here is the defintion.
Given a universe $U$ a collection of sets $\mathcal{A}=\{S_i\}$ and a function $\varphi:U\to\{-1,1\}$. For $S\...
- 136
1
vote
Upper Bound for distance-two chromatic number in terms of maximum degree
Let $\Delta$ denote the maximum degree of $G$.
The bound $\Delta^2+1$ cannot be improved significantly.
For instance, even for a colouring variant called 2-ranking (which is a generalisation of ...
- 1,723
Only top scored, non community-wiki answers of a minimum length are eligible