4 votes

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) \...
Chandra Chekuri's user avatar
2 votes

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\...
TheHolyJoker's user avatar
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 ...
Cyriac Antony's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible