A graph has an
‐coloring
if there exists an assignment from the vertices to subsets of with size such that adjacent vertices are assigned disjoint subsets. Odd girth at least is a necessary condition for a graph to have a ‐coloring. Chen and Raspaud conjectured a tight upper bound on the maximum average degree of a graph with odd girth at least that guarantees a ‐coloring. Namely, they conjectured that every graph with odd girth at least and maximum average degree less than has a ‐coloring. This conjecture is true for ; when , computers were used to perform case analysis. The main result of this paper confirms the conjecture for the next open case () without the use of computers. Moreover, our approach yields simpler, computer‐free proofs for previously known cases ().
A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a color appearing exactly once in its open neighborhood. We prove that every finite simple graph with girth at least 7 and maximum average degree less than 8/3 admits a proper conflict-free coloring from arbitrary vertex lists of size at least the vertex degree plus 2. Consequently, every planar graph of girth at least 8 is proper conflict-free (degree+2)-choosable, improving the sufficient girth bound of 9 obtained from the earlier 18/7 maximum-average-degree theorem. The proof uses local extension lemmas for short threads, including threads with a common boundary endpoint. Two-element control sets and an incidence count yield a weighted thread inequality, which supplies the required bound on the charge sent by each vertex in a discharging argument.
Given a graph $G=(V,E)$, a (proper) $k$-coloring for $G$ is a vertex coloring with $k$ colors such that every two adjacent vertices receive different colors. Suppose that the vertex set $V$ is partitioned into some groups, a proper coloring is called fair if for every color class, the difference between the number of vertices in any two groups does not exceed a given threshold. In this paper, we investigate the parameterized complexity of the fair coloring problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the number of groups for forests and also graphs of modular-width two, even when the number of colors is equal to two. On the positive side, we prove that when the number of colors is equal to two, then the problem is FPT with respect to neighborhood diversity of the input graph. Moreover, in general, the problem is FPT with respect to neighborhood diversity and the number of groups. As a by-product, we prove that unary vector bin packing problem is W[1]-hard with respect to the dimension.
R. Javadi, Hossein Shokouhi· arXiv.org· 0 citations
A proper conflict-free coloring is a proper vertex coloring in which every nonisolated vertex has a color occurring uniquely in its open neighborhood. We prove that every graph with neither a $K_5$-minor nor a $Q_6$-minor admits such a coloring with at most seven colors, where $Q_6=K_3\vee\overline{K_3}$. In particular, this improves the previous general upper bound of eight for planar graphs. The proof combines a previously developed iterated distance-three selector construction with a general anchor-contraction lifting principle. The first supplies independently colored witnesses in closed neighborhoods, while the second combines those witnesses with a proper coloring of a suitable minor. We also develop the parity analogue of the first mechanism and show that, whenever the $K_{k+1}$ case of Hadwiger's conjecture holds, every $K_{k+1}$-minor-free graph can be proper vertex colored with $2k-1$ colors such that every nonisolated vertex has a color occurring an odd number of times in its open neighborhood.
A. Jiménez, C. Lintzmayer, M. Sambinelli· 1 citation
We introduce and begin the study of sequence b-colorings, a natural generalization of the classical notion of b-colorings introduced by Irving and Manlove in 1999. In a sequence b-coloring, each color class is required to contain a prescribed minimum number of color-dominating vertices (CDVs). We establish several fundamental properties of the associated parameters, prove that every sequence is realizable, and show that the problem of deciding whether a particular graph realizes a particular sequence is NP-complete. We also characterize the sequences realized by cycles, obtain results on regular graphs with prescribed girth, and investigate colorings requiring one additional CDV, including a characterization of connected graphs with chromatic number $3$ for which no such coloring exists.
Some equity constraints on the coloring classes of a classical coloring of the vertices of a graph give rise to the equitable coloring: the number of vertices colored with each color differs by at most one. The least number of colors for which a graph has such an equitable coloring is called the equitable chromatic number. In this paper a new integer programming model is introduced based on a stable set formulation for the decision version of the Equitable Coloring Problem. This new formulation is integrated into two Binary Search-like algorithms, the efficiency of which we have tested on thirty-two instances from literature. The numerical results show that this new approach was able to improve the known lower bounds of equitable chromatic number for two thirds of the tested instances and found the equitable coloring number for two instances.
History: Accepted by Andrea Lodi, Design & Analysis of Algorithms–Discrete.
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1294 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1294 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
E. F. Olariu, C. Frăsinaru· INFORMS journal on computing· 0 citations
A b-coloring is a proper vertex coloring such that every color class contains a vertex, a so-called b-vertex, which sees all colors in its closed neighborhood. This type of coloring has been intensively studied from both structural and algorithmic point of view. Recently, Zaker [DAM 2025] introduced the notion of a b*-coloring, which is a b-coloring in which there is a vertex that sees a b-vertex of every color in its closed neighborhood. The b*-chromatic number is the maximum integer k such that there is a b*-coloring with k colors. We partially answer a question posed by Zaker and prove that graphs of girth at least 7 are b*-monotonic, which means that the b*-chromatic number does not increase by taking an induced subgraph. In addition, we discover a class of d-regular graphs of girth at least 5 with b*-chromatic number d+1, which strengthens a result about b-colorings by Dettlaff, Furma\'nczyk, Peterin, Roux, and Ziemann [AMC 2024]. We also study the parameterized complexity of finding b*-colorings, and show that for many structural parameters, the complexity coincides with that of finding b-colorings. In particular, the b*-chromatic number can be computed in polynomial time on any class of bounded clique-width. For most parameters, the translation from b-colorings is straightforward but for the feedback edge number, the FPT algorithm for b*-colorings is actually much simpler than that for b-colorings by Balab\'an [MFCS 2026].
Jakub Balabán, Oliver Bukor· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
