More Like this

1. Immersions and Albertson’s Conjecture

   https://doi.org/10.4230/LIPIcs.SoCG.2025.50  

   Fox, Jacob; Pach, János; Suk, Andrew (January 2025, 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
2. A Unified Proof of Conjectures on Cycle Lengths in Graphs

   https://doi.org/10.1093/imrn/rnaa324  

   Gao, Jun; Huo, Qingyi; Liu, Chun-Hung; Ma, Jie (January 2021, International Mathematics Research Notices)

   null (Ed.)

   Abstract In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph $$G$$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $$k$$; in addition, if $$G$$ is $$2$$-connected and non-bipartite, then it contains cycles of all lengths modulo $$k$$. 2. For all $$k\geq 3$$, every $$k$$-connected graph contains a cycle of length zero modulo $$k$$. 3. Every $$3$$-connected non-bipartite graph with minimum degree at least $k+1$ contains $$k$$ cycles of consecutive lengths. 4. Every graph with chromatic number at least $k+2$ contains $$k$$ cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible. 

   more » « less
3. A Note on the Gyárfás–Sumner Conjecture

   https://doi.org/10.1007/s00373-024-02754-z  

   Nguyen, Tung; Scott, Alex; Seymour, Paul (April 2024, Graphs and Combinatorics)

   The Gyárfás–Sumner conjecture says that for every tree T and every integer t ≥ 1, if G is a graph with no clique of size t and with sufficiently large chromatic number, then G contains an induced subgraph isomorphic to T. This remains open, but we prove that under the same hypotheses, G contains a subgraph H isomorphic to T that is “path-induced”; that is, for some distinguished vertex r, every path of H with one end r is an induced path of G. 

   more » « less
4. Graphs with Tunable Chromatic Numbers for Parallel Coloring

   https://doi.org/10.1137/1.9781611976229.6  

   Cheng, Xin; Maji, Hemanta; Pothen, Alex (January 2020, SIAM 2020 Workshop on Combinatorial Scientific Computing)

   We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are well-bounded) for testing graph coloring algorithms on parallel computers. For the distance-1 graph coloring problem, we identify three classes of graphs with this property. The first is the Erdős-Rényi random graph with prescribed expected degree, where the chromatic number is known with high probability. It is also known that the Greedy algorithm colors this graph using at most twice the number of colors as the chromatic number. The second is a random geometric graph embedded in hyperbolic space where the size of the maximum clique provides a tight lower bound on the chromatic number. The third is a deterministic graph described by Mycielski, where the graph is recursively constructed such that its chromatic number is known and increases with graph size, although the size of the maximum clique remains two. For Jacobian estimation, we bound the distance-2 chromatic number of random bipartite graphs by considering its equivalence to distance-1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance-2 chromatic number. The regimes of graph sizes and probabilities that we consider are chosen to suit the Jacobian estimation problem, where the number of columns and rows are asymptotically nearly equal, and have number of nonzeros linearly related to the number of columns. Computationally we verify the theoretical predictions and show that the graphs are often be colored optimally by the serial and parallel Greedy algorithms. 

   more » « less
5. A Graph Coloring Technique for Identifying The Minimum Number of Parts for Physical Integration in Product Design

   Gopalakrishnan, Praveen; Cavallaro, Jeffry; Jahanbekam, Sogol; Behdad, Sara (August 2019, the ASME 2019 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference, IDETC/CIE, Aug 18-21, 2019, Anaheim, CA.)

   The objective of this study is to develop a mathematical framework for determining the minimum number of parts required in a product to satisfy a list of functional requirements (FRs) given a set of connections between FRs. The problem is modeled as a graph coloring technique in which a graph G with n nodes (representing the FRs) and m edges (representing the connections between the FRs) is studied to determine the graph’s chromatic number c(G), which is the minimum number of colors required to properly color the graph. The chromatic number of the graph represents the minimum number of parts needed to satisfy the list of FRs. In addition, the study calculates the computational efficiency of the proposed algorithm. Several examples are provided to show the application of the proposed algorithm. 

   more » « less