The Experts below are selected from a list of 2499 Experts worldwide ranked by ideXlab platform

Wood, David R. - One of the best experts on this subject based on the ideXlab platform.

  • Clustered Coloring of Graphs Excluding a Subgraph and a Minor
    2020
    Co-Authors: Liu Chun-hung, Wood, David R.
    Abstract:

    A graph coloring has bounded clustering if each Monochromatic Component has bounded size. Equivalently, it is a partition of the vertices into induced subgraphs with bounded size Components. This paper studies clustered colorings of graphs, where the number of colors depends on an excluded minor and/or an excluded subgraph. We prove the following results (for fixed integers $s,t$ and a fixed graph $H$). First we show that graphs with no $K_{s,t}$ subgraph and with no $H$-minor are $(s+2)$-colorable with bounded clustering. The number of colors here is best possible. This result implies that graphs with no $K_{s+1}$-minor are $(s+2)$-colorable with bounded clustering, which is within two colors of the clustered coloring version of Hadwiger's conjecture. For graphs of bounded treewidth (or equivalently, excluding a planar minor) and with no $K_{s,t}$ subgraph, we prove $(s+1)$-choosability with bounded clustering, which is best possible. We then consider excluding an odd minor. We prove that graphs with no $K_{s,t}$ subgraph and with no odd $H$-minor are $(2s+1)$-colorable with bounded clustering, generalizing a result of the first author and Oum who proved the case $s=1$. Moreover, at least $s-1$ color classes are stable sets. Finally, we consider the clustered coloring version of a conjecture of Gerards and Seymour and prove that graphs with no odd $K_{s+1}$-minor are $(8s-4)$-colorable with bounded clustering, which improves on previous such bounds.Comment: The paper together with the original version of arXiv:1905.08969 and arXiv:1908.05597 are merged into a new version of arXiv:1905.08969 in order to give a more throughout picture of the theory we buil

  • Clustered Graph Coloring and Layered Treewidth
    2020
    Co-Authors: Liu Chun-hung, Wood, David R.
    Abstract:

    A graph coloring has bounded clustering if each Monochromatic Component has bounded size. This paper studies clustered coloring, where the number of colors depends on an excluded complete bipartite subgraph. This is a much weaker assumption than previous works, where typically the number of colors depends on an excluded minor. This paper focuses on graph classes with bounded layered treewidth, which include planar graphs, graphs of bounded Euler genus, graphs embeddable on a fixed surface with a bounded number of crossings per edge, amongst other examples. Our main theorem says that for fixed integers $s,t,k$, every graph with layered treewidth at most $k$ and with no $K_{s,t}$ subgraph is $(s+2)$-colorable with bounded clustering. In the $s=1$ case, which corresponds to graphs of bounded maximum degree, we obtain polynomial bounds on the clustering. This greatly improves a corresponding result of Esperet and Joret for graphs of bounded genus. The $s=3$ case implies that every graph with a drawing on a fixed surface with a bounded number of crossings per edge is 5-colorable with bounded clustering. Our main theorem is also a critical Component in two companion papers that study clustered coloring of graphs with no $K_{s,t}$-subgraph and excluding a fixed minor, odd minor or topological minor

  • Clustered 3-Colouring Graphs of Bounded Degree
    2020
    Co-Authors: Dujmović Vida, Esperet Louis, Morin Pat, Walczak Bartosz, Wood, David R.
    Abstract:

    A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every Monochromatic Component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O(\Delta^2)$. The previous best bound was $O(\Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $\Delta$ that exclude a fixed minor are 3-colourable with clustering $O(\Delta^5)$. The best previous bound for this result was exponential in $\Delta$.Comment: arXiv admin note: text overlap with arXiv:1904.0479

  • Clustered 3-Colouring Graphs of Bounded Degree
    'Cambridge University Press (CUP)', 2020
    Co-Authors: Dujmović Vida, Esperet Louis, Morin Pat, Walczak Bartosz, Wood, David R.
    Abstract:

    A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every Monochromatic Component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O(\Delta^2)$. The previous best bound was $O(\Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $\Delta$ that exclude a fixed minor are 3-colourable with clustering $O(\Delta^5)$. The best previous bound for this result was exponential in $\Delta$

  • Clustered Coloring of Graphs Excluding a Subgraph and a Minor
    2020
    Co-Authors: Liu Chun-hung, Wood, David R.
    Abstract:

    A graph coloring has bounded clustering if each Monochromatic Component has bounded size. Equivalently, it is a partition of the vertices into induced subgraphs with bounded size Components. This paper studies clustered colorings of graphs, where the number of colors depends on an excluded minor and/or an excluded subgraph. We prove the following results (for fixed integers $s,t$ and a fixed graph $H$). First we show that graphs with no $K_{s,t}$ subgraph and with no $H$-minor are $(s+2)$-colorable with bounded clustering. The number of colors here is best possible. This result implies that graphs with no $K_{s+1}$-minor are $(s+2)$-colorable with bounded clustering, which is within two colors of the clustered coloring version of Hadwiger's conjecture. For graphs of bounded treewidth (or equivalently, excluding a planar minor) and with no $K_{s,t}$ subgraph, we prove $(s+1)$-choosability with bounded clustering, which is best possible. We then consider excluding an odd minor. We prove that graphs with no $K_{s,t}$ subgraph and with no odd $H$-minor are $(2s+1)$-colorable with bounded clustering, generalizing a result of the first author and Oum who proved the case $s=1$. Moreover, at least $s-1$ color classes are stable sets. Finally, we consider the clustered coloring version of a conjecture of Gerards and Seymour and prove that graphs with no odd $K_{s+1}$-minor are $(8s-4)$-colorable with bounded clustering, which improves on previous such bounds

S Moriyama - One of the best experts on this subject based on the ideXlab platform.

Esperet Louis - One of the best experts on this subject based on the ideXlab platform.

  • Clustered 3-Colouring Graphs of Bounded Degree
    2020
    Co-Authors: Dujmović Vida, Esperet Louis, Morin Pat, Walczak Bartosz, Wood, David R.
    Abstract:

    A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every Monochromatic Component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O(\Delta^2)$. The previous best bound was $O(\Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $\Delta$ that exclude a fixed minor are 3-colourable with clustering $O(\Delta^5)$. The best previous bound for this result was exponential in $\Delta$.Comment: arXiv admin note: text overlap with arXiv:1904.0479

  • Clustered 3-Colouring Graphs of Bounded Degree
    'Cambridge University Press (CUP)', 2020
    Co-Authors: Dujmović Vida, Esperet Louis, Morin Pat, Walczak Bartosz, Wood, David R.
    Abstract:

    A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every Monochromatic Component has at most $c$ vertices. We prove that planar graphs with maximum degree $\Delta$ are 3-colourable with clustering $O(\Delta^2)$. The previous best bound was $O(\Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $\Delta$ that exclude a fixed minor are 3-colourable with clustering $O(\Delta^5)$. The best previous bound for this result was exponential in $\Delta$

  • Surfaces have (asymptotic) dimension 2
    HAL CCSD, 2020
    Co-Authors: Bonamy Marthe, Esperet Louis, Bousquet Nicolas, Groenland Carla, Pirot François, Scott Alex
    Abstract:

    34 pages, 4 figuresThe asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e.\ colorings in which each Monochromatic Component has small weak diameter. In this paper, we prove that for any $p$, the class of graphs excluding $K_{3,p}$ as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with Monochromatic Components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal

  • Surfaces have (asymptotic) dimension 2
    2020
    Co-Authors: Bonamy Marthe, Esperet Louis, Bousquet Nicolas, Groenland Carla, Pirot François, Scott Alex
    Abstract:

    The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e. colorings in which each Monochromatic Component has small weak diameter. In this paper, we prove that for any $p$, the class of graphs excluding $K_{3,p}$ as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with Monochromatic Components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal.Comment: 35 pages, 4 figures - v3: correction of the statements of Theorem 5.2, Corollary 5.3 and Theorem 5.9. Most of the results in this paper have been merged to arXiv:2012.0243

Scott Alex - One of the best experts on this subject based on the ideXlab platform.

  • Surfaces have (asymptotic) dimension 2
    HAL CCSD, 2020
    Co-Authors: Bonamy Marthe, Esperet Louis, Bousquet Nicolas, Groenland Carla, Pirot François, Scott Alex
    Abstract:

    34 pages, 4 figuresThe asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e.\ colorings in which each Monochromatic Component has small weak diameter. In this paper, we prove that for any $p$, the class of graphs excluding $K_{3,p}$ as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with Monochromatic Components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal

  • Surfaces have (asymptotic) dimension 2
    2020
    Co-Authors: Bonamy Marthe, Esperet Louis, Bousquet Nicolas, Groenland Carla, Pirot François, Scott Alex
    Abstract:

    The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e. colorings in which each Monochromatic Component has small weak diameter. In this paper, we prove that for any $p$, the class of graphs excluding $K_{3,p}$ as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with Monochromatic Components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal.Comment: 35 pages, 4 figures - v3: correction of the statements of Theorem 5.2, Corollary 5.3 and Theorem 5.9. Most of the results in this paper have been merged to arXiv:2012.0243

Debiasio Louis - One of the best experts on this subject based on the ideXlab platform.

  • A note about Monochromatic Components in graphs of large minimum degree
    2020
    Co-Authors: Debiasio Louis, Krueger, Robert A.
    Abstract:

    For all positive integers $r\geq 3$ and $n$ such that $r^2-r$ divides $n$ and an affine plane of order $r$ exists, we construct an $r$-edge colored graph with minimum degree $(1-\frac{r-2}{r^2-r})n-2$ such that the largest Monochromatic Component has order less than $\frac{n}{r-1}$. This generalizes an example of Guggiari and Scott and, independently, Rahimi for $r=3$ and thus disproves a conjecture of Gy\'arf\'as and S\'ark\"ozy for all integers $r\geq 3$ such that an affine plane of order $r$ exists.Comment: 11 pages, 3 figure

  • Large Monochromatic Components in 3-edge-colored Steiner triple systems
    2020
    Co-Authors: Debiasio Louis, Tait Michael
    Abstract:

    It is known that in any $r$-coloring of the edges of a complete $r$-uniform hypergraph, there exists a spanning Monochromatic Component. Given a Steiner triple system on $n$ vertices, what is the largest Monochromatic Component one can guarantee in an arbitrary 3-coloring of the edges? Gy\'arf\'as proved that $(2n+3)/3$ is an absolute lower bound and that this lower bound is best possible for infinitely many $n$. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually $(1-o(1))n$. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest \emph{3-partite hole} (that is, sets $X_1, X_2, X_3$ with $|X_1|=|X_2|=|X_3|$ such that no edge intersects all of $X_1, X_2, X_3$) in the Steiner triple system (Gy\'arf\'as previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the coloring has a particular structure. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.Comment: Updated to address referee comments; to appear in Journal of Combinatorial Design

  • Monochromatic balanced Components, matchings, and paths in multicolored complete bipartite graphs
    2019
    Co-Authors: Debiasio Louis, Krueger, Robert A., Gyárfás András, Ruszinkó Miklós, Sárközy, Gábor N.
    Abstract:

    It is well-known that in every $r$-coloring of the edges of the complete bipartite graph $K_{n,n}$ there is a Monochromatic connected Component with at least ${2n\over r}$ vertices. It would be interesting to know whether we can additionally require that this large Component be balanced; that is, is it true that in every $r$-coloring of $K_{n,n}$ there is a Monochromatic Component that meets both sides in at least $n/r$ vertices? Over forty years ago, Gy\'arf\'as and Lehel and independently Faudree and Schelp proved that any $2$-colored $K_{n,n}$ contains a Monochromatic $P_n$. Very recently, Buci\'c, Letzter and Sudakov proved that every $3$-colored $K_{n,n}$ contains a Monochromatic connected matching (a matching whose edges are in the same connected Component) of size $\lceil n/3 \rceil$. So the answer is strongly "yes" for $1\leq r\leq 3$. We provide a short proof of (a non-symmetric version of) the original question for $1\leq r\leq 3$; that is, every $r$-coloring of $K_{m,n}$ has a Monochromatic Component that meets each side in a $1/r$ proportion of its part size. Then, somewhat surprisingly, we show that the answer to the question is "no" for all $r\ge 4$. For instance, there are $4$-colorings of $K_{n,n}$ where the largest balanced Monochromatic Component has $n/5$ vertices in both partite classes (instead of $n/4$). Our constructions are based on lower bounds for the $r$-color bipartite Ramsey number of $P_4$, denoted $f(r)$, which is the smallest integer $\ell$ such that in every $r$-coloring of the edges of $K_{\ell,\ell}$ there is a Monochromatic path on four vertices. Furthermore, combined with earlier results, we determine $f(r)$ for every value of $r$.Comment: 9 pages, 2 figures, to appear in Journal of Combinatoric

  • Large Monochromatic Components in multicolored bipartite graphs
    2019
    Co-Authors: Debiasio Louis, Krueger, Robert A., Sárközy, Gábor N.
    Abstract:

    It is well-known that in every $r$-coloring of the edges of the complete bipartite graph $K_{m,n}$ there is a Monochromatic connected Component with at least ${m+n\over r}$ vertices. In this paper we study an extension of this problem by replacing complete bipartite graphs by bipartite graphs of large minimum degree. We conjecture that in every $r$-coloring of the edges of an $(X,Y)$-bipartite graph with $|X|=m$, $|Y|=n$, $\delta(X,Y) > \left( 1 - \frac{1}{r+1}\right) n$ and $\delta(Y,X) > \left( 1 - \frac{1}{r+1}\right) m$, there exists a Monochromatic Component on at least $\frac{m+n}{r}$ vertices (as in the complete bipartite graph). If true, the minimum degree condition is sharp (in that both inequalities cannot be made weak when $m$ and $n$ are divisible by $r+1$). We prove the conjecture for $r=2$ and we prove a weaker bound for all $r\geq 3$. As a corollary, we obtain a result about the existence of Monochromatic Components with at least $\frac{n}{r-1}$ vertices in $r$-colored graphs with large minimum degree.Comment: 14 pages, to appear in Journal of Graph Theor