The List Edge-Coloring Conjecture predicts that any graph whose edges can be colored with $k$ colors can also be colored from arbitrary lists of $k$ colors. We prove its stronger online form for two new infinite families, $K_{p-1}$ and $K_{2p}$, where $p$ is an odd prime. For even $n$, order the vertices of $K_n$ and draw each perfect matching as arcs above them. Count crossings separately within each matching, and let $S_n$ be the number of decompositions into perfect matchings having an even total crossing count minus the number having an odd total. Then \[ S_{p-1}\equiv\left(\frac{-2}{p}\right)\pmod p, \qquad S_{2p}\equiv-p\pmod {p^2}. \] The two congruences are governed by the same elementary matching sum over $\F_p$, although their proofs use the prime $p$ differently. Their nonzero residues give the conjectured values even in the online game. They also treat the corresponding complete graphs with one perfect matching removed, as well as $K_{2p}$ after deleting some, but not all, of a natural cyclic family of $p$ disjoint perfect matchings.
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...
Let $G$ be a graph. Under an \emph{injective edge coloring} of $G$, any two edges at distance $2$ or belonging to a common triangle receive distinct colors. The \emph{injective chromatic index} of $G$, denoted by $\chi'_{inj}(G)$, is the smallest integer $k$ such that $G$ admits an injective edge coloring with $k$ colo...
Let $G$ be a graph together with a total order $\prec$ on its edges. We say that $\prec$ is realizable in $\mathbb{R}^d$ if there is a placement of the vertices of $G$ in $\mathbb{R}^d$ such that the Euclidean lengths of the edges induce exactly the order $\prec$. Almendra-Hern\'andez and Mart\'inez-Sandoval proved tha...
Gerardo L. Maldonado, Leonardo Martínez-Sandoval, Miguel Raggi et al.· 0 citations
For $k, r, n$ natural numbers let $\rho_{r,k}(K_n)$ be the number of $r$-edge-colorings of $K_n$ that do not contain a rainbow copy of a $K_k$, that is, a copy of $K_k$ in which all edges receive different colors. When $k=3$, the quantity $\rho_{r,3}(K_n)$ represents the number of Gallai Colorings. It was proved by Bal...
Let $G$ be a simple graph with maximum degree $\Delta\ge 3$, and let $P(G,k)$ denote its chromatic polynomial. For each positive integer $k$, the list-color function $P_{\ell}(G,k)$ is the minimum number of $L$-colorings of $G$ over all $k$-assignments $L$. In this paper, we prove that $P_{\ell}(G,k)=P(G,k)$ for every...
A strong odd $k$-coloring of a graph $G$ is a proper $k$-coloring such that every color appearing in the neighborhood of a non-isolated vertex appears an odd number of times. The minimum $k$ for which $G$ admits a strong odd $k$-coloring is the \emph{strong odd chromatic number}, denoted by $\chi_{\text{so}}(G)$, of $G...
D. Pradhan, V. Sharma, Shaily Verma· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
