Zobrazeno 1 - 10
of 111
pro vyhledávání: '"05C15, 05C10"'
A coloring of the edges of a graph $G$ in which every $K_{1,2}$ is totally multicolored is known as a proper coloring and a coloring of the edges of $G$ in which every $K_{1,2}$ and every $K_{2,2}$ is totally multicolored is called a B-coloring. In t
Externí odkaz:
http://arxiv.org/abs/2408.09081
Autor:
Berger, Eli, Guo, He
A result \cite{matcomp} from 2006 of Aharoni and the first author of this paper states that for any two natural numbers p, q, where p divides q, if a matroid M is p-colorable and a matroid N is q-colorable then M \cap N is (p+q)-colorable. In this pa
Externí odkaz:
http://arxiv.org/abs/2407.09160
We study simplicial complexes (hypergraphs closed under taking subsets) that are the intersection of a given number k of matroids. We prove bounds on their chromatic numbers (the minimum number of edges required to cover the ground set) and their lis
Externí odkaz:
http://arxiv.org/abs/2407.08789
We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (non-trivial) snark that can be embedded in the p
Externí odkaz:
http://arxiv.org/abs/2405.16586
We study the problem of finding homomorphisms into odd cycles from planar graphs with high odd-girth. The Jaeger-Zhang conjecture states that every planar graph of odd-girth at least $4k+1$ admits a homomorphism to the odd cycle $C_{2k+1}$. The $k=1$
Externí odkaz:
http://arxiv.org/abs/2402.02689
One of Thomassen's classical results is that every planar graph of girth at least $5$ is 3-choosable. One can wonder if for a planar graph $G$ of girth sufficiently large and a $3$-list-assignment $L$, one can do even better. Can one find $3$ disjoin
Externí odkaz:
http://arxiv.org/abs/2312.17233
Autor:
Cranston, Daniel W.
Wegner conjectured that if $G$ is a planar graph with maximum degree $\Delta\ge 8$, then $\chi(G^2)\le \left\lfloor \frac32\Delta\right\rfloor +1$. This problem has received much attention, but remains open for all $\Delta\ge 8$. Here we prove an ana
Externí odkaz:
http://arxiv.org/abs/2308.09585
Autor:
Cortés, Pedro P., Kumar, Pankaj, Moore, Benjamin, de Mendez, Patrice Ossona, Quiroz, Daniel A.
A $k$-subcolouring of a graph $G$ is a function $f:V(G) \to \{0,\ldots,k-1\}$ such that the set of vertices coloured $i$ induce a disjoint union of cliques. The subchromatic number, $\chi_{\textrm{sub}}(G)$, is the minimum $k$ such that $G$ admits a
Externí odkaz:
http://arxiv.org/abs/2306.02195
Autor:
Deniz, Zakir
A vertex coloring of a graph $G$ is said to be a 2-distance coloring if any two vertices at distance at most $2$ from each other receive different colors, and the least number of colors for which $G$ admits a $2$-distance coloring is known as the $2$
Externí odkaz:
http://arxiv.org/abs/2212.03831
Autor:
Jendroľ, Stanislav, Onderko, Alfréd
An $r$-hued coloring of a simple graph $G$ is a proper coloring of its vertices such that every vertex $v$ is adjacent to at least $\min\{r, \deg(v)\}$ differently colored vertices. The minimum number of colors needed for an $r$-hued coloring of a gr
Externí odkaz:
http://arxiv.org/abs/2211.01041