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 work

Try 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.

  • 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”
    Try filter

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.

Recent Combinatorics papers

5 recent papers
  • Sahab Hajebi, Penny Haxell

    Abstract

    We study the reconfiguration of independent transversals in graphs with a prescribed vertex partition. Given a graph GG with a vertex partition V=(V1,…,Vm)\mathcal{V}=(V_1,\ldots,V_m), an independent transversal is an independent set containing exactly one vertex from each part ViV_i of V\mathcal{V}. 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 r∈Nr\in\mathbb{N} and ε>0ε>0, we present a polynomial-time algorithm that, given an rr-claw-free graph GG with a vertex partition V=(V1,…,Vm)\mathcal{V}=(V_1,\ldots,V_m) and two independent transversals SS and RR, either finds a polynomial-length reconfiguration path between SS and RR, or identifies a nonempty set of partition classes B⊆V\mathcal{B}\subseteq\mathcal{V} such that the subgraph induced by their union admits a strong dominating set of size at most (2+ε)∣B∣(2+ε)|\mathcal{B}|. 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 rr-uniform bipartite hypergraphs H=(A,B,E)H=(A,B,E), that either produces a polynomial-length reconfiguration path between two given perfect matchings or identifies a subset S⊆AS\subseteq A whose link hypergraph ESE_S in BB 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 λ(G)λ(G) be the least kk for which labels from {0,…,k}\{0,\ldots,k\} suffice, and let \laml(G)\laml(G) be its arbitrary-real-list counterpart. Our two main results are an eight-element list theorem for fullerenes and the universal bound λ(G)≤708587λ(G)\le708587 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 q≥7q\ge7 diagonal colors, with an optimal uniform threshold. For cubic 3-connected plane graphs we obtain λ≤14λ\le14, improving to λ≤9λ\le9 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.