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: Hyperbolic families and coloring graphs on surfaces
We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities.  more » « less
Award ID(s):
1700157
PAR ID:
10087346
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Transactions of the American Mathematical Society. Series B
Volume:
5
ISSN:
2330-0000
Page Range / eLocation ID:
167-221
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Graphs and Combinatorics)
    Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable. 
    more » « less
  2. ; ; ; ; (, European Symposium on Algorithms)
    For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of Pt-free graphs. We show that for every odd k ≥ 5 the Ck-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P9-free graphs. On the other hand, we prove that the extension version of Ck-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw. 
    more » « less
  3. ; ; (, Journal of Graph Theory)
    ABSTRACT If is a list assignment of colors to each vertex of an ‐vertex graph , then anequitable‐coloringof is a proper coloring of vertices of from their lists such that no color is used more than times. A graph isequitably‐choosableif it has an equitable ‐coloring for every ‐list assignment . In 2003, Kostochka, Pelsmajer, and West (KPW) conjectured that an analog of the famous Hajnal–Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer every graph with maximum degree at most is equitably ‐choosable. The main result of this paper is that for each and each planar graph , a stronger statement holds: if the maximum degree of is at most , then is equitably ‐choosable. In fact, we prove the result for a broader class of graphs—the class of the graphs in which each bipartite subgraph with has at most edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in , in particular, for all planar graphs. We also introduce the new stronger notion ofstrongly equitable(SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE ‐choosable, then it is both equitably ‐choosable and equitably ‐colorable, while neither of being equitably ‐choosable and equitably ‐colorable implies the other. 
    more » « less
  4. ; ; ; (, Advances in Combinatorics)
    A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 
    more » « less
  5. ; (, The Electronic Journal of Combinatorics)
    Gyárfas proved that every coloring of the edges of $$K_n$$ with $t+1$ colors contains a monochromatic connected component of size at least $n/t$. Later, Gyárfás and Sárközy asked for which values of $$\gamma=\gamma(t)$$ does the following strengthening for almost complete graphs hold: if $$G$$ is an $$n$$-vertex graph with minimum degree at least $$(1-\gamma)n$$, then every $(t+1)$-edge coloring of $$G$$ contains a monochromatic component of size at least $n/t$. We show $$\gamma= 1/(6t^3)$$ suffices, improving a result of DeBiasio, Krueger, and Sárközy. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email