math.CO Mathematics
Combinatorics papers on arXiv
Follow graph theory, enumeration, extremal problems, and other combinatorics in math.CO. A mathematical object or problem family is a useful filter when broad combinatorial language overlaps many areas.
2,556 papers indexed
Follow the whole category with the official math.CO RSS feed, or use a personal filter to select keywords and authors. See the arXiv RSS feed guide for setup and the category guide for primary and cross-listed subjects.
Filter ideas for Combinatorics
How filters workTry a distinctive object name before adding a theorem keyword. Names and abbreviations are literal search terms, so include common variants in an OR group when needed.
- Try filter
Graph coloring
Add graph or a specific coloring problem; an OR group can also include the spelling colouring.
Category math.CO + abstract contains “coloring” - Try filter
Extremal combinatorics
Pair extremal with the structure you study, such as a graph, hypergraph, or set system.
Category math.CO + abstract contains “extremal”
Examples are starting points. Preview them before saving; keyword matches do not assess a paper’s quality. Recent papers below use the primary category; saved category filters also match cross-listed categories.
LATEST SUBMISSIONS
Recent Combinatorics papers
Sahab Hajebi, Penny Haxell
Abstract
We study the reconfiguration of independent transversals in graphs with a prescribed vertex partition. Given a graph with a vertex partition , an independent transversal is an independent set containing exactly one vertex from each part of . The reconfiguration problem concerns transforming one independent transversal into another through a sequence of local changes, while preserving the independent transversal property at every step. For any fixed and , we present a polynomial-time algorithm that, given an -claw-free graph with a vertex partition and two independent transversals and , either finds a polynomial-length reconfiguration path between and , or identifies a nonempty set of partition classes such that the subgraph induced by their union admits a strong dominating set of size at most . Our result provides an algorithmic counterpart to recent connectivity results for the reconfiguration graph of all independent transversals, and establishes polynomial bounds on its diameter under suitable conditions. As a specific application, we obtain a polynomial-time algorithm for reconfiguring perfect matchings in -uniform bipartite hypergraphs , that either produces a polynomial-length reconfiguration path between two given perfect matchings or identifies a subset whose link hypergraph in has a small cover.
Bidwan Chakraborty
Abstract
We study the independence complexes of Cartesian products of paths and cycles. Let G(m,n) denote the Cartesian product of the path P_m and the cycle C_n, and let Delta(m,n) denote its independence complex. We determine the well-covered graphs in this family and use reduced homology to study their Cohen-Macaulay and Buchsbaum properties. Using these results, we completely classify the Cohen-Macaulay members. We then study the Buchsbaum property of Delta(m,n) through vertex links. For the remaining family P_m x C_3, we introduce an auxiliary family of graphs and use an inductive link argument together with Reisner's criterion to determine precisely when the independence complex of P_m x C_3 is Buchsbaum. Combining this with the remaining well-covered cases yields the complete Buchsbaum classification.
Usama Waheed, Naveed Ahmed Azam
Abstract
A graph is said to be determined by the spectrum of a graph-associated matrix if no nonisomorphic graph shares the same spectrum with it. In this paper, we introduce the average flow matrix of a connected graph and study its spectral properties. We investigate its effectiveness in distinguishing graphs by carrying out a computational enumeration of connected graphs having a cospectral mate with respect to this matrix up to order 10. Our computations show that every connected graph on at most 10 vertices is determined by the spectrum of the average flow matrix. To the best of our knowledge, this is the first graph-associated matrix for which the spectrum distinguishes all connected graphs of order at most 10.
Zhou Guofei
Abstract
In this paper we study proper vertex labelings of 3-connected plane graphs that give distinct boundary-vertex sums to faces sharing an edge. Let be the least for which labels from suffice, and let be its arbitrary-real-list counterpart. Our two main results are an eight-element list theorem for fullerenes and the universal bound for all 3-connected plane graphs. We establish structural nine- and eight-color bounds, classify triangulations whose vertices of degree at least five form an independent set, and determine their exact diagonal chromatic numbers. We also prove closure under triangular sums for diagonal colors, with an optimal uniform threshold. For cubic 3-connected plane graphs we obtain , improving to in the bipartite case.
Aida Abiad, Ronan Egan, Stef Mohnen
Abstract
Switching is a local operation that preserves specified properties of a combinatorial object. It has been used to derive constructions of inequivalent Hadamard matrices and nonisomorphic cospectral graphs. In this paper we investigate the relation between these constructions for real and Butson Hadamard matrices. We show that, while equivalent matrices have isomorphic associated graphs, the converse can fail for Butson matrices. We prove that a character decomposition determines the graph spectrum from the singular values of entrywise powers. For prime phase, we also observe that the spectrum depends only on the order and phase; for composite phase, a switching preserving the Butson property can change it. We show that Orrick's closed-quadruple and Hall-set switchings correspond to Wang-Qiu-Hu switching, up to graph isomorphism. Going in the other direction, we characterise when the Godsil-McKay and Wang-Qiu-Hu reflections preserve the Butson property and give phase-multiplicity conditions for the corresponding graph switchings. Finally we also relate block switching to cyclic graph switching under a phase-balance condition, automatic at prime phase. These results provide a basis for transferring tools and techniques between matrix switching and graph switching.
Frequently asked questions
How do I get alerts for new Combinatorics papers on arXiv?
Create a filter for the math.CO category — add keywords or authors to narrow it further if you like. Matching papers are delivered to a personal RSS feed, and optionally by immediate, daily, or weekly email digest.
Where does this Combinatorics paper data come from?
Paper metadata comes directly from arXiv through its official OAI-PMH feed, checked roughly every 15 minutes for new submissions in math.CO and every other arXiv category.