For an edge $uv$ of a finite simple graph $G$, its imbalance is $|d_G(u)-d_G(v)|$, and the imbalance multiset $M_G$ consists of the imbalances of all edges of $G$. Kozerenko and Skochko conjectured that $M_G$ is graphic whenever every edge has positive imbalance. We prove this conjecture. The main ingredient is the following capacity bound: for every set $A$ of $k$ edges, \[ \sum_{e\in E(G)\setminus A}\min\{k,\operatorname{imb}_G(e)\} \ge k\max\{\Delta-k,0\}, \] where $\Delta$ is the maximum degree of $G$. This bound yields all Erd\H{o}s--Gallai inequalities directly; a parity computation completes the proof.
Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the su...
For a graph $G$, let $L(G)=\max\{\omega(G),\lceil (|V(G)|+1)/(\alpha_{\min}(G)+1)\rceil\}$, where $\omega(G)$ is the clique number and $\alpha_{\min}(G)$ is the minimum, over all vertices $v$, of the largest size of an independent set containing $v$. Dybizba\'nski, Furma\'nczyk, and Mkrtchyan (Discrete Appl. Math. 354...
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular...
For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put \[ I_G(\sigma)=|E(G)\cap E(\sigma(G))|. \] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In 1977 Erd\H{o}s...
A $(k,d)$-edge coloring of a loopless multigraph $G$ is an edge coloring using at most $k$ colors such that the subgraph formed by each color class has maximum degree at most $d$. The least such $k$ is denoted by $\chi'_d(G)$. Let $G$ be a loopless non-bipartite multigraph with maximum degree $\Delta(G)$ and odd girth...
For a graph $G$, let $\psi(G)=\max\{\chi(G[V(C)]):C$ is an odd cycle of $G\}$, with $\psi(G)=0$ when $G$ is bipartite. For positive integers $N$, set $F(N)=\max\{\chi(G)-\psi(G):|V(G)|\le N\}$. The function $F$ measures the finite-order additive gap arising from an open problem of Erdos and Hajnal. We prove $N^{1/6-o(1...
Shu-Yan Chen· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
