A vertex-coloring of a graph is centered if every connected subgraph has a vertex with a unique color. A vertex-coloring of a graph is linear if every path in the graph has a vertex with a unique color. Let $\chi_{\mathrm{cen}}(G)$ and $\chi_{\mathrm{lin}}(G)$ be the minimum number of colors in a centered (resp. linear) coloring of $G$. We present a family of graphs witnessing that if $f$ is a nondecreasing function such that $\chi_{\mathrm{cen}}(G) \leq f(\chi_{\mathrm{lin}}(G))$ for every graph $G$, then $f(k) = \Omega(k^2 / \log k)$. The construction was found by OpenAI's GPT-5.6 Sol Pro.
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 edge colorings of graphs, SIAM J. Discrete Math. 40 (2026) 897--904), which states that $\chi_k'(G)\leq k+o(k)$ for every $0_k$-graph $G$. We prove a lower bound for $0_k$-graphs with degree set $\{k,2k\}$ and a specified vertex partition. With a suitable choice of the part sizes, if the number of edges inside one part is $o(k^2)$, then $\chi_k'(G)\geq(4-2\sqrt2+o(1))k$. This gives connected bipartite and connected nonbipartite counterexamples. In particular, the same examples also disprove the earlier conjecture of Botler, Colucci, and Kohayakawa (The mod $k$ chromatic index of graphs is $O(k)$, J. Graph Theory 102 (2023) 197--200), which states that $\chi_k'(G)\leq k+C$ for some absolute constant $C$.
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 $g_0(G)$, and let $d\ge1$ be odd. We prove that \[ \chi'_d(G)\le\left\lceil\frac{g_0(G)\Delta(G)-1}{dg_0(G)-1}\right\rceil. \] For $d=1$, this is Goldberg's odd-girth refinement of Shannon's theorem, while for $g_0(G)=3$ it is the defective Shannon bound of Aboulker, Aubian, and Huang. For every odd $d>1$, every odd $g_0\ge3$, and every $\Delta>d$, an almost full ring multigraph $R(\Delta,g_0)$, an odd cycle with edge multiplicities alternating between $\lfloor\Delta/2\rfloor$ and $\lceil\Delta/2\rceil$, except that two consecutive edges have multiplicity $\lfloor\Delta/2\rfloor$, attains equality. We also derive a range in which the defective Goldberg--Seymour conjecture holds.
For a graph $G$, let $h(G)$ be the minimum cardinality of a vertex set meeting every maximum independent set of $G$. We establish two complementary reduction principles for the Bollob\'as--Erd\H{o}s--Tuza conjecture: the conjecture for arbitrary graphs is equivalent to its restriction to regular graphs of any fixed positive linear degree, and, within every hereditary graph class, a uniform sublinear bound is equivalent to a sublinear bound on graphs of every fixed positive linear vertex connectivity. We prove the sharp general estimate \[ h(G)\le \left\lfloor\frac{|V(G)|}{2\alpha(G)+\delta(G)-|V(G)|}\right\rfloor \] whenever the denominator is positive, with equality for balanced complete multipartite graphs. Consequently, every $3$-colorable graph of order $n$ with $\kappa(G)\ge\rho n$ and $\rho>1/3$ has a hitting set of size at most $\lfloor(\rho-1/3)^{-1}\rfloor$; direct use of a $3$-coloring improves this to $6$ when $\kappa(G)>4n/9$ and to the sharp bound $3$ when $\kappa(G)>n/2$. For dense regular graphs with independence ratio greater than $1/4$, we obtain a logarithmic bound, while constructions with linear degree and linear independence number show that $h(G)=\Omega(\sqrt n)$ can still occur. We also prove a logarithmic bound for near-regular $3$-colorable graphs and exhibit a critical family at connectivity $n/3$ that explains the limitations of the degree-surplus and degree-ratio methods.
We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its original one. We define the stable chromatic number $\chi_\mathrm{stable}(G)$ of a graph $G$ as the minimum integer $k$ such that every preference profile admits a stable $k$-coloring of $G$. We establish several upper and lower bounds. In particular, for any acyclic orientation of the edges of $G$, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on $\chi_\mathrm{stable}(G)$. This shows that $\chi_\mathrm{stable}(G)$ is well-defined. We also show that $O(t \log (1+n/t))$ colors suffice for an $n$-vertex graph $G$ of treewidth $t$, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable $k$-colorability is NP-complete for every fixed $k\ge 3$. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.
Tomohiro Koana, Y. Oh, Hirotaka Yoneda· 0 citations
A majority C-coloring of a graph $G$ assigns colors to the vertices such that every vertex shares its color with at least half of its neighbors. The maximum number of colors that can be used in such a coloring of $G$ is denoted by $\overline{\chi}_{\geqslant}(G)$. In this paper, the focus is on the majority C-coloring in Cartesian product graphs. It is shown that $\overline{\chi}_{\geqslant}(G \square H) \ge \overline{\chi}_{\geqslant}(G) \overline{\chi}_{\geqslant}(H)$ gives a sharp lower bound, but the difference also can be arbitrarily large. For two-dimensional Hamming graphs, the exact value $\overline{\chi}_{\geqslant}(K_m \square K_n) = \min\{m,n\}$ is established. Balanced Hamming graphs of higher dimension, that is the $k$th powers of complete graphs with respect to the Cartesian product, are also studied. It is proved that $\overline{\chi}_{\geqslant}(K_n^{\square, k})= n^{k/2}$ holds for every even integer $k$. If $k$ is odd and the Hamming graph is the $k$-dimensional hypercube, then $\overline{\chi}_{\geqslant}(K_2^{\square, k})= 2^{\lfloor k/2\rfloor}$. On the other hand, a majority C-coloring of $K_n^{\square, k}$ with at least $3 n^{\lfloor k/2\rfloor}/2 $ colors is presented for every $n \ge 7$ and odd $k \ge 3$. For Cartesian grids, the main result shows that $\overline{\chi}_{\geqslant}(P_m \square P_n) = 1 + \lfloor m/2\rfloor \lfloor n/2\rfloor$ if at least one of $m$ and $n$ is odd, while $\overline{\chi}_{\geqslant}(P_m \square P_n)=mn/4$ holds if both parameters are even and $m \ge n \ge 4$. The paper concludes with a conjecture and several open problems.
Csilla Bujtás, M. Dettlaff, Hanna Furmanczyk et al.· 0 citations
A path in a properly edge-colored graph is rainbow if its edges have pairwise distinct colors. For a proper edge-coloring $c$ of a graph $G$, let $\operatorname{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\operatorname{rpc}(G)$ be the maximum of $\operatorname{rpc}(G,c)$ over all proper edge-colorings of $G$. We prove that, for every fixed $0<\alpha<1$, every properly edge-colored $n$-vertex graph with minimum degree at least $\alpha n$ satisfies $\operatorname{rpc}(G,c)\leq(1+o(1))n/2$, where the coefficient $1/2$ is best possible. We also determine $\operatorname{rpc}(G)$ asymptotically for every complete multipartite graph. If $G=K_{n_1,\ldots,n_r}$ has order $n$ and largest and smallest part sizes $M$ and $s$, respectively, then, uniformly over all choices of the number and sizes of the parts, $\operatorname{rpc}(G)=(1+o(1))\max\{\min\{\lfloor n/2\rfloor,n-M\},(n-s)/2\}$. The proof combines pseudorandom packings of globally rainbow linear forests with a decomposition into dense parts and prescribed avoidance for arbitrary dense graphs, and with reserved connectors and a direct dominant-part argument for complete multipartite graphs.
Xiao-Chuan Liu, Boyan Xu, Xu Yang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
