skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: On the Gonality of Ferrers Rook Graphs
A Ferrers rook graph is a graph whose vertices correspond to the dots in a Ferrers diagram, and where two vertices are adjacent if they are in the same row or the same column.  We propose a conjectural formula for the gonality of Ferrers rook graphs, and prove this conjecture for a few infinite families of Ferrers diagrams.  We also prove the conjecture for all Ferrers diagrams F with |F| ≤ 8.  more » « less
Award ID(s):
2054135
PAR ID:
10642278
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
PUMP Journal of Undergraduate Research
Date Published:
Journal Name:
The PUMP Journal of Undergraduate Research
Volume:
8
ISSN:
2765-8724
Page Range / eLocation ID:
70 to 84
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Combinatorics, Probability and Computing)
    null (Ed.)
    Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 
    more » « less
  2. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Aichholzer, Oswin; Wang, Haitao (Ed.)
    A graph is said to contain K_k (a clique of size k) as a weak immersion if it has k vertices, pairwise connected by edge-disjoint paths. In 1989, Lescure and Meyniel made the following conjecture related to Hadwiger’s conjecture: Every graph of chromatic number k contains K_k as a weak immersion. We prove this conjecture for graphs with at most 1.4(k-1) vertices. As an application, we make some progress on Albertson’s conjecture on crossing numbers of graphs, according to which every graph G with chromatic number k satisfies cr(G) ≥ cr(K_k). In particular, we show that the conjecture is true for all graphs of chromatic number k, provided that they have at most 1.4(k-1) vertices and k is sufficiently large. 
    more » « less
  3. ; ; (, Journal of Graph Theory)
    ABSTRACT We prove that for any graph , the total chromatic number of is at most . This saves one color in comparison with the result of Hind from 1992. In particular, our result says that if , then has a total coloring using at most colors. When is regular and has a sufficient number of vertices, we can actually save an additional two colors. Specifically, we prove that for any , there exists such that: if is an ‐regular graph on vertices with , then . This confirms the Total Coloring Conjecture for such graphs . 
    more » « less
  4. ; (, Annual Symposium on Foundations of Computer Science)
    An efficient implicit representation of an n-vertex graph G in a family F of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most 2^O(n log(n)) graphs on n vertices, and thus has at most factorial speed of growth. The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length n^Ω(1). 
    more » « less
  5. ; ; ; (, SIAM Journal on Discrete Mathematics)
    We prove that every connected P5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P5-free graph G with independence number at least three contains a three-vertex induced path with vertices a-b-c in order, such that every neighbor of c is also adjacent to one of a,b. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email