CS Paper Radar

Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number

Siddhesh Chaubal

cs.DM math.CO ·submitted 2026-10-29 06:07 UTC · v1

Abstract

A set $S$ of vertices of a graph $G$ is a mutual-visibility set if every pair of vertices of $S$ is joined by a shortest path whose internal vertices avoid $S$, and the mutual-visibility chromatic number $χ_μ(G)$ is the least number of mutual-visibility sets into which $V(G)$ can be partitioned. Klavžar, Kuziak, Valenzuela Tripodoro and Yero (2025) proved that $χ_μ(G)\leχ(G)$ whenever $G$ has diameter two, observed that equality holds for complete bipartite graphs, and asked whether there are any other diameter-two graphs attaining equality. We answer this question in the affirmative. We construct a graph $G_{11}$ of order 11 and diameter two with $χ_μ(G_{11})=χ(G_{11})=3$, and an infinite family of such graphs obtained from $G_{11}$ by replacing one vertex with pairwise non-adjacent copies of it.

Comment
8 pages, 3 figures. Submitted to Aequationes Mathematicae

Closest papers

Nearest neighbours by meaning across the whole index.

Mutual-visibility k-colouring is NP-complete for every fixed diameter

cs.DM cs.CCmath.CO ·2026-10-31 ·Siddhesh Chaubal
similarity 0.84
Abstract · 9 pages, 1 figure. v2: extended to any fixed number k of colours; new title

A mutual-visibility set in a graph G is a set S of vertices such that any two vertices of S are connected by a shortest path with no internal vertex in S, and the mutual-visibility chromatic number $χ_μ(G)$ is the minimum number of mutual-visibility sets needed to partition V(G). Babu, Di Stefano and Lakshmanan showed that it is NP-complete to decide whether $χ_μ(G)\le 2$ for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed $d\ge2$; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed $k\ge2$ and $d\ge2$, it is NP-complete to decide whether $χ_μ(G)\le k$ for graphs of diameter d. The proof rests on a reformulation of $χ_μ(G)\le 2$ for diameter-two graphs as the 2-colourability of an associated hypergraph, and on a reduction from 2-colourability of 3-uniform hypergraphs without short cycles.

0.24

Counterexamples to a conjecture and improved bounds for bipanchromatic colorings

cs.DM math.CO ·2026-10-19 ·Stefan Novaković, Duško Jojić
theory similarity 0.67
Abstract · 10 pages, 2 figures

We study the bipanchromatic number $χ_B$, introduced by Lalou et al. (Discrete Appl. Math. 391 (2026), 511-522) as the maximum number of colors in a panchromatic hypergraph coloring where every color appears at least twice. They show that merging uniquely occurring colors in a maximum panchromatic coloring gives the lower bound $β=χ_P-\lceilα/2\rceil \leq χ_B$, where $χ_P$ is the panchromatic number and $α$ is the minimum number of such colors among maximum panchromatic colorings. They conjectured that $χ_B=β$ and subsequently disproved it (arXiv:2610.08042). We identify the smallest counterexample, with six vertices and three hyperedges, both minimum possible. We show that the ratio bound $χ_B/β<2$ is asymptotically sharp and prove minimality results for the order and hyperedge count. For $3\leα<χ_P$ we show that every integer from $β$ to $χ_P-1$ occurs as $χ_B$ while $χ_P$ and $α$ are held fixed. Furthermore, we discover that the values $|V|,χ_P,α$ directly decide whether the conjectured equality holds except when $α=4$, where a matching reduction resolves the ambiguity. We derive the optimal universal lower bound $L$ depending only on $|V|,χ_P,α$ in the nontrivial regime $0<2α<|V|$. Finally, we prove $χ_B/L\le5/4$ and $χ_B/L\le6/5+1/(5L)$, with $5/4$ sharp and $6/5$ asymptotically sharp as $L\to\infty$.

0.11

Biplanar graphs with independence number two are 9-colorable

cs.LO math.CO ·2026-09-23 ·Stefan Szeider
theoryhot direction similarity 0.67
Abstract

A graph is biplanar if it is the union of two planar graphs on the same vertex set. The largest chromatic number of a biplanar graph is known to lie between 9 and 12. The lower bound comes from Sulanke's graph, which has independence number 2, and a biplanar graph on 19 vertices with independence number 2 would have chromatic number at least 10. Gethner and Sulanke asked in 2009 whether such a graph exists. We show that it does not, and more generally that every biplanar graph with independence number at most 2 is 9-colorable. The proof embeds a hypothetical counterexample in the union of two sphere triangulations, enumerates with SAT modulo symmetries the 3271 graphs that pass a necessary filter for the complement of such a union, and shows with a SAT solver that none of them is such a complement; a matching argument reduces the general statement to this computation and one further case on 18 vertices. The computational part of the proof, including the completeness of the enumeration and every refutation, is checked in Lean 4, assuming three classical facts about planar graphs. The Lean development, the SAT instances, and the enumeration certificates are available on Zenodo.

0.24

Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable

cs.DM math.CO ·2026-09-04 ·Matheus Adauto, Celina de Figueiredo, Diana Sasaki, Rafael Schneider
similarity 0.66
Abstract

A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder $L_{12}$ admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph $G$, each color class consists of an independent set $S$ together with a perfect matching of $G-S$. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even $n\geq16$, some connected cubic graph of order $n$ admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.

0.20

Large diameter for $(Δ+2)$-colouring reconfiguration

cs.DM math.CO ·2026-11-12 ·Wouter Cames van Batenburg
similarity 0.66
Abstract · 15 pages, 2 figures

Given a graph $G$ and an integer $k$, the reconfiguration graph $\mathcal{R}_{k}(G)$ has the proper $k$-colourings of $G$ for vertices, two of which are adjacent if and only if they differ on precisely one vertex of $G$. In $2022$, Cambie, Cranston and the author proved that the diameter of $\mathcal{R}_{Δ+2}(G)$ is at most $n+2μ$, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of $\mathcal{R}_{Δ+2}(G)$ is precisely equal to $n + μ$, for every graph $G$ with $n$ vertices, matching number $μ$ and maximum degree $Δ$. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least $n+\frac{3}{2}μ-2$. We also provide counterexamples that are $Δ$-regular, we show that every graph has reconfiguration diameter at least $n+\frac{1}{2} μ$, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.

0.25

Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound

cs.DM math.CO ·2026-09-27 ·Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Sangita Saha, Saumya Sen
theory similarity 0.65
Abstract · 14 pages, 2 figures

A strong edge colouring of a graph $G$ is an edge colouring in which every colour class is an induced matching. The minimum number of colours is the strong chromatic index $χ'_s(G)$. If each edge $e$ is assigned a list $L'(e)$ and its colour must belong to $L'(e)$, the corresponding parameter is the strong list chromatic index $χ'_{s,\ell}(G)$. From the definitions, $χ'_s(G)\leχ'_{s,\ell}(G)$. Barrett et al. gave an $8$-approximation for strong edge colouring on unit disk graphs and Grelier et al. improved the approximation factor to $6$. Our first result extends this factor-$6$ guarantee from unit disk graphs to the strictly larger class of disk graphs. In another direction, Erdős and Nešetřil conjectured that the strong chromatic index of a graph of maximum degree $Δ$ is asymptotically at most $1.25Δ^2$. The best published general asymptotic upper bound has leading coefficient $1.772$, due to Hurley et al. For unit disk graphs, Dębski et al. proved that $χ'_s(G) \leq 1.625 Δ^2$. Our second result improves this leading coefficient to $225/142 \approx 1.5845$. In fact, the proof establishes a stronger bound $χ'_{s,\ell}(G)\le\frac{225}{142} Δ^2+O(Δ)$ for unit disk graphs.

0.22

Complexity and algorithms for proper conflict-free coloring in graphs

cs.DM math.CO ·2026-08-11 ·Dinabandhu Pradhan, Vaishali Sharma
similarity 0.65
Abstract

A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every non-isolated vertex $v\in V(G)$. The PCF chromatic number, denoted by $χ_{pcf}(G)$, is the least integer $k$ such that there exists a PCF $k$-coloring of $G$. Given a graph $G$ and a positive integer $k$, PCF $k$-COLORABILITY is to decide whether $G$ admits a PCF $k$-coloring. Ahn et al. [Discrete Appl. Math. 377 (2025) 10-17] proved that PCF $k$-COLORABILITY is NP-complete for bipartite graphs. We strengthen this result by proving that PCF $k$-COLORABILITY is NP-complete for perfect elimination bipartite graphs, which is a proper subclass of bipartite graphs. We also show that the PCF chromatic number of a graph cannot be approximated within $O(n^{1-\varepsilon})$ unless P=NP, for any $\varepsilon>0$. On the positive side, we provide linear-time algorithms for PCF $k$-COLORABILITY in block graphs, proper interval graphs, chain graphs, and pseudo-split graphs. We show that $χ_{pcf}(G)\leq ω(G)+1$ for block graphs, proper interval graphs, and pseudo-split graphs (except $C_5$), and we characterize all graphs for which the equality holds.

0.41

Elementary graphs are chromatic-choosable

cs.DM math.CO ·2026-10-12 ·Narayanan N, Nandana K. Vasudevan, K. Somasundaram
theory similarity 0.63
Abstract · 13 page, 5 figures, 1 table

A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$, confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray--Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.

0.34