Pith. sign in

REVIEW 2 major objections 3 minor 38 references

The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number

T0 review · 2 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the r-dynamic chromatic number of any graph is controlled by its strong 2-coloring number, giving the linear bound (k−1)r+1 whenever scol2(G) ≤ k.

desk verdict Clean main bound, two repairable proof slips. read the letter →

arxiv 2501.13617 v1 pith:ZG2O7RKX submitted 2025-01-23 math.CO cs.DM

Miriam Goetze , Torsten Ueckerdt This is my paper · ORCID
classification math.COcs.DM MSC 05C1505C1005C83
keywords r-dynamiccoloringstrong2-coloringnumberboundedexpansiontreewidthrow-treewidthr-huedgraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the r-dynamic chromatic number of a graph is controlled by its strong 2-coloring number: if no ordering of the vertices forces any vertex to have more than k earlier vertices within distance two (with later internal vertices allowed), then (k−1)r+1 colors suffice for an r-dynamic coloring. Because many sparse graph classes—planar graphs, bounded-treewidth graphs, and every graph class of bounded expansion—have bounded strong 2-coloring numbers, the result implies their r-dynamic chromatic numbers grow at most linearly with r even when maximum degree is unbounded. The paper also turns the general bound into explicit constants for treewidth and row-treewidth, and notes that subdividing every edge of a graph at least twice yields 2r+1 colors regardless of the original graph.

What carries the argument

The engine is the strong 2-coloring number $\mathrm{scol}_2(G)$, the minimum over all linear vertex orders of the largest set of vertices that can reach a fixed vertex by a path of length at most two whose internal vertices come later in the order. The argument rides on a greedy coloring that maintains two invariants: strong propriety (a vertex never shares a color with an earlier vertex from which it is reachable by such a path) and weak $r$-dynamicity at every vertex. The counting step bounds the two kinds of forbidden colors separately, and Zhu's theorem identifying bounded expansion exactly with bounded strong coloring numbers (Theorem 4) converts the parameter bound into a statement about whole graph classes.

What would settle it

Enumerate all graphs on up to eight vertices, compute $\mathrm{scol}_2(G)$ exactly over all vertex orders, and compare $\chi_r(G)$ with $(k-1)r+1$ for small $r$; a single violation would refute Theorem 5, while a 4-cycle check isolates whether the proof's clique claim must be replaced by the mutual $2$-accessibility argument.

Watch

Extended reading notes

Core claim

The central claim is Theorem 5: for all $r,k\in\mathbb{N}$, if $\mathrm{scol}_2(G)\le k$ then $\chi_r(G)\le (k-1)r+1$. The proof colors vertices one at a time in an order witnessing the strong 2-coloring number, maintaining a 'strongly proper' coloring—no two vertices within distance two that are ordered consistently receive the same color—and a per-vertex condition that each neighborhood already uses $\min(r,\deg(v))$ colors. At each step it counts at most $k-1$ forbidden colors from distance-two constraints and at most $(k-1)(r-1)$ from the dynamic-color constraint, so the total stays below $(k-1)r+1$. Corollary 6 then states that for any graph class of bounded expansion, the $r$-dynamic chromatic numbers of its graphs are bounded by a linear function of $r$.

Load-bearing premise

The proof's greedy step leans on the claim that the earlier neighbors of the newly added vertex form a clique, so that a proper coloring already distinguishes them; this can fail for an optimal order (a 4-cycle is a counterexample), and the replacement argument via mutual $2$-accessibility is not given in the paper.

Editorial extensions

If this is right

  • For every graph class of bounded expansion, there is a constant $c$ such that $\chi_r(G)\le c\cdot r$ for all graphs in the class and all $r$, with no dependence on maximum degree.
  • Graphs of treewidth $k$ satisfy $\chi_r(G)\le k\cdot r+1$.
  • Graphs of row-treewidth $k$ satisfy $\chi_r(G)\le 5k\cdot r+1$.
  • For $(g,k)$-planar graphs, $\chi_r(G)\le 5(4g+6)(k+1)r+1$, giving a linear-in-$r$ and linear-in-genus bound that generalizes earlier planar and genus results.
  • Every graph obtained by subdividing each edge at least twice satisfies $\mathrm{scol}_2(S)\le 3$ and hence $\chi_r(S)\le 2r+1$, even though the class of such subdivisions need not have bounded expansion.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The additive-versus-multiplicative question the paper raises for treewidth suggests the $(k-1)r+1$ bound is probably not tight; a natural next step is to decide whether $\chi_r(G)$ can be kept in $O(\mathrm{tw}(G)+r)$ for all graphs.
  • Because the stated clique justification for one proof step can fail on a 4-cycle, the theorem's correctness depends on replacing that step with a mutual $2$-accessibility argument; a reader checking the proof should confirm that replacement before relying on the bound.
  • The same greedy two-invariant scheme may transfer to other parameters that are bounded on sparse classes, such as the weak coloring number or generalized coloring numbers, yielding similar linear bounds for other distance-type colorings.
  • The discussion of subdividing every edge at least twice shows the hypothesis 'bounded expansion' is sufficient but not necessary: some classes with unbounded expansion still have linear $r$-dynamic chromatic number, so the true boundary of the phenomenon lies elsewhere.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper proves that for every graph G and integer r, the r-dynamic chromatic number satisfies chi_r(G) <= (scol2(G)-1)r+1, where scol2 is the strong 2-coloring number. It then derives that every graph class of bounded expansion has r-dynamic chromatic numbers bounded by a linear function of r, and it provides explicit bounds in terms of treewidth and row-treewidth. The proofs are short and rely on a greedy extension argument together with known bounds on strong coloring numbers. The paper also discusses limitations of generalizing the result to nowhere dense classes and gives an example of a somewhere dense class with bounded r-dynamic chromatic number.

Significance. If correct, the main result is a clean and useful generalization: it subsumes several earlier bounds for planar graphs, bounded-genus graphs, and minor-closed classes under the single framework of strong coloring numbers, and it gives the first linear-in-r bound for all bounded-expansion classes. The paper is a concise note that connects r-dynamic coloring to well-studied sparsity parameters, and the proof of Theorem 5 is conceptually attractive. The explicit bound for treewidth is also of independent interest. However, two specific issues in the current manuscript—an incorrect justification in the proof of Theorem 5 and a constant error in the row-treewidth corollary—need to be repaired before the paper can be accepted.

major comments (2)
  1. [Section 3, proof of Theorem 5] The justification of property 1 is false. The paper states that the neighborhood of v_{i+1} in G_{i+1} is a clique, but for an arbitrary linear order witnessing scol2(G) <= k this need not hold; e.g., for C4 with order v1,v2,v3,v4, the earlier neighbors of v4 are v1 and v3, which are not adjacent, and this order satisfies scol2 <= 3. The conclusion is nevertheless salvageable: if a and b are two earlier neighbors of v_{i+1} with a < b, then the path a-v_{i+1}-b has length 2 and its inner vertex v_{i+1} is greater than b, so a belongs to SReach2(b); since phi_i is strongly proper, phi_i(a) != phi_i(b). Thus all earlier neighbors of v_{i+1} receive distinct colors and property 1 holds. Please replace the clique argument with this mutual 2-accessibility argument.
  2. [Section 4, Lemma 13 and Corollary 14] There is a constant error in the row-treewidth bound. Lemma 13 with t=2 gives scol2(G) <= 5(rtw(G)+1), not 5 rtw(G). Substituting into Theorem 5 yields chi_r(G) <= (5 rtw(G)+4)r+1, not the claimed 5 rtw(G) r+1. The same issue affects Theorem 3(3) in the introduction. The bound remains linear in r, but all three statements (Theorem 3(3), Lemma 13 as applied, and Corollary 14) need to be corrected consistently.
minor comments (3)
  1. [Section 4, Lemma 7] In the proof of Lemma 7, the sentence 'This already proves that scol1(G) <= k+1' uses a reverse perfect elimination ordering; it may be helpful to explicitly note that a perfect elimination ordering is one where right neighborhoods form cliques, so reversing it makes left neighborhoods cliques.
  2. [Section 3, after Theorem 5] The paragraph discussing the subdivision example says 'scol1(K'_n) <= 3', but the argument uses that all original vertices appear before subdivision vertices; this is clear but a short explanation of why scol1 is at most 3 would improve readability.
  3. [Section 5, Lemma 15] In Lemma 15, the assertion that SReach2(u) = {u} for every original vertex u relies on the fact that each edge is subdivided at least twice, so original vertices are at distance at least 3 from each other; this is correct but could be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 5 is a direct greedy derivation from the definition of scol2; the notable defect is a repairable correctness gap, not a circularity.

full rationale

The paper's central claim, Theorem 5, does not reduce to its inputs by construction. The strong 2-coloring number scol2 is an independently defined graph parameter, and the proof greedily extends a coloring using only the bound |SReach2(v)| <= k and the definitions of strong properness and weak r-dynamicity. No fitted constants, no parameter estimation, and no hidden restatement of the conclusion appear in the argument. Corollary 6 follows by combining Theorem 5 with Zhu's external characterization of bounded expansion via bounded strong coloring numbers; this is an imported theorem, not an assumption of the target result. The row-treewidth bounds in Lemma 13 and Corollary 14 are proven directly by a counting argument over layers, and the cited prior work on row-treewidth supplies definitions and background bounds, not the r-dynamic conclusion. The authors do cite their own earlier work (e.g., the row-treewidth paper), but those citations are not load-bearing for the main theorem and do not smuggle in the desired result. The proof does contain a genuine correctness gap: the justification of property 1 claims the earlier neighborhood of v_{i+1} is a clique, which is false for an arbitrary optimal scol2 order. However, this is a bug in the written proof, not a circularity; it does not make the theorem equivalent to its assumptions, and the gap is repairable by observing that any two earlier neighbors of v_{i+1} are mutually 2-accessible and therefore receive distinct colors in a strongly proper coloring. Thus, despite the correctness gap, the derivation chain is not circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities. The proof relies on standard graph-theoretic definitions and a few cited external theorems; none of these assume the target result.

assumptions (5)
  • standard math Strong k-coloring number definition and the existence of an order minimizing max |SReach_k(v)|.
    Foundation of Theorem 5; standard definition, no independent verification needed.
  • domain assumption Zhu's characterization: a class has bounded expansion iff scolk is bounded for every k.
    Used to derive Corollary 6 from Theorem 5; cited as Theorem 4 from [37].
  • standard math Lemma 7: scolt(G) <= tw(G)+1.
    Proved in the paper (Section 4); relies on perfect elimination orderings for k-trees.
  • domain assumption Van den Heuvel-Wood bound on scolt for (g,k)-planar graphs.
    External result cited as Lemma 10; used for Corollary 11.
  • domain assumption Dujmovic et al. result that planar graphs and bounded-genus graphs have bounded row-treewidth.
    Justifies the claim in the abstract that planar graphs are covered by the row-treewidth bound; cited as [7, Theorem 37].

how reviews work

0 comments
Cite this review

Pith. "Pith review of The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number." pith.science (2026). https://pith.science/paper/ZG2O7RKX

@misc{pith2026250113617,
  author       = {Pith},
  title        = {Pith review of: The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZG2O7RKX}},
  note         = {Machine review of arXiv:2501.13617}
}
abstract

A proper vertex-coloring of a graph is $r$-dynamic if the neighbors of each vertex $v$ receive at least $\min(r, \mathrm{deg}(v))$ different colors. In this note, we prove that if $G$ has a strong $2$-coloring number at most $k$, then $G$ admits an $r$-dynamic coloring with no more than $(k-1)r+1$ colors. As a consequence, for every class of graphs of bounded expansion, the $r$-dynamic chromatic number is bounded by a linear function in $r$. We give a concrete upper bound for graphs of bounded row-treewidth, which includes for example all planar graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 25 canonical work pages

  1. [1]

    Prosenjit Bose, Vida Dujmovi \'c , Mehrnoosh Javarsineh, Pat Morin, and David R. Wood. Separating layered treewidth and row treewidth. Discrete Mathematics & Theoretical Computer Science , 24(Graph Theory), 2022. https://doi.org/0.46298/dmtcs.7458 doi:0.46298/dmtcs.7458

    work page 2022

  2. [2]

    Asymptotically optimal vertex ranking of planar graphs, 2022

    Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh, and Pat Morin. Asymptotically optimal vertex ranking of planar graphs, 2022. URL: https://arxiv.org/abs/2007.06455, https://arxiv.org/abs/2007.06455 arXiv:2007.06455

    arXiv 2022

  3. [3]

    Graphs with linearly bounded R amsey numbers

    GT Chen and Richard H Schelp. Graphs with linearly bounded R amsey numbers. Journal of Combinatorial Theory, Series B , 57(1):138--149, 1993. https://doi.org/10.1006/jctb.1993.1012 doi:10.1006/jctb.1993.1012

    arXiv 1993

  4. [4]

    Graph r-hued colorings— A survey

    Ye Chen, Suohai Fan, Hong-Jian Lai, and Murong Xu. Graph r-hued colorings— A survey. Discrete Applied Mathematics , 321:24--48, 2022. https://doi.org/10.1016/j.dam.2022.06.003 doi:10.1016/j.dam.2022.06.003

    work page doi:10.1016/j.dam.2022.06.003 2022

  5. [5]

    Improved bounds for centered colorings

    Micha D e bski, Stefan Felsner, Piotr Micek, and Felix Schröder. Improved bounds for centered colorings. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2212--2226. https://doi.org/10.1137/1.9781611975994.136 doi:10.1137/1.9781611975994.136

    work page doi:10.1137/1.9781611975994.136 2020

  6. [6]

    Adjacency labelling for planar graphs (and beyond)

    Vida Dujmovi\' c , Louis Esperet, Cyril Gavoille, Gwena\" e l Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). Journal of the ACM , 68(6), 2021. https://doi.org/10.1145/3477542 doi:10.1145/3477542

    doi:10.1145/3477542 2021

  7. [7]

    Vida Dujmovi\' c , Gwena\" e l Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. Journal of the ACM , 67(4), 2020. https://doi.org/10.1145/3385731 doi:10.1145/3385731

    doi:10.1145/3385731 2020

  8. [8]

    Vida Dujmović, Louis Esperet, Pat Morin, and David R. Wood. Proof of the clustered H adwiger conjecture. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1921--1930, 2023. https://doi.org/10.1109/FOCS57990.2023.00116 doi:10.1109/FOCS57990.2023.00116

    arXiv 2023

Show all 38 references
  1. [9]

    On comparable box dimension

    Zden e k Dvo r \' a k, Daniel Gon c alves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On comparable box dimension. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry (SoCG 2022) , volume 224 of Leibniz International Proceed...

    2022 doi

  2. [10]

    Boxicity, poset dimension, and excluded minors

    Louis Esperet and Veit Wiechert. Boxicity, poset dimension, and excluded minors. Electronic Journal of Combinatorics , 2018. https://doi.org/10.37236/7787 doi:10.37236/7787

    2018 doi

  3. [11]

    Coloring and covering nowhere dense graphs

    Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. Coloring and covering nowhere dense graphs. SIAM Journal on Discrete Mathematics , 32(4):2467--2481, 2018. https://doi.org/10.1137/18M1168753 doi:10.1137/18M1168753

    2018 doi

  4. [12]

    Deciding first-order properties of nowhere dense graphs

    Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM , 64(3), 2017. https://doi.org/10.1145/3051095 doi:10.1145/3051095

    2017 doi

  5. [13]

    List colouring squares of planar graphs

    Fr \'e d \'e ric Havet, Jan Van Den Heuvel, Colin McDiarmid, and Bruce Reed. List colouring squares of planar graphs. Electronic Notes in Discrete Mathematics , 29:515--519, 2007. https://doi.org/10.1016/j.endm.2007.07.079 doi:10.1016/j.endm.2007.07.079

    2007 doi

  6. [14]

    Odd colourings, conflict-free colourings and strong colouring numbers

    Robert Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. The Australasian Journal of Combinatorics , 87:160--164, 2023. URL: https://ajc.maths.uq.edu.au/pdf/87/ajc_v87_p160.pdf

    2023

  7. [15]

    A simple competitive graph coloring algorithm

    Hal A Kierstead. A simple competitive graph coloring algorithm. Journal of Combinatorial Theory, Series B , 78(1):57--68, 2000. https://doi.org/10.1006/jctb.1999.1927 doi:10.1006/jctb.1999.1927

  8. [16]

    Planar graph coloring with an uncooperative partner

    Hal A Kierstead and William T Trotter. Planar graph coloring with an uncooperative partner. Journal of Graph Theory , 18(6):569--584, 1994. https://doi.org/10.1002/jgt.3190180605 doi:10.1002/jgt.3190180605

    1994 doi

  9. [17]

    Orderings on graphs and game coloring number

    Hal A Kierstead and Daqing Yang. Orderings on graphs and game coloring number. Order , 20:255--264, 2003. https://doi.org/10.1023/B:ORDE.0000026489.93166.cb doi:10.1023/B:ORDE.0000026489.93166.cb

    2003

  10. [18]

    Kierstead and William T

    Henry A. Kierstead and William T. Trotter. Competitive colorings of oriented graphs. Electronic Journal of Combinatorics , 2001. https://doi.org/10.37236/1611 doi:10.37236/1611

    2001 doi

  11. [19]

    Dynamic coloring of graphs having no K5 minor

    Younjin Kim, Sang June Lee, and Sang-il Oum. Dynamic coloring of graphs having no K5 minor. Discrete Applied Mathematics , 206:81--89, June 2016. https://doi.org/10.1016/j.dam.2016.01.022 doi:10.1016/j.dam.2016.01.022

    2016 doi

  12. [20]

    A survey on the distance-colouring of graphs

    Florica Kramer and Horst Kramer. A survey on the distance-colouring of graphs. Discrete Mathematics , 308(2-3):422--426, 2008. https://doi.org/10.1016/j.disc.2006.11.059 doi:10.1016/j.disc.2006.11.059

    2008 doi

  13. [21]

    Conditional colorings of graphs

    Hong-Jian Lai, Jianliang Lin, Bruce Montgomery, Taozhi Shui, and Suohai Fan. Conditional colorings of graphs. Discrete Mathematics , 306(16):1997--2004, 2006. https://doi.org/10.1016/j.disc.2006.03.052 doi:10.1016/j.disc.2006.03.052

    1997 doi

  14. [22]

    Upper bounds of dynamic chromatic number

    Hong-Jian Lai, Bruce Montgomery, and Hoifung Poon. Upper bounds of dynamic chromatic number. Ars Combinatoria , 68(3):193--201, 2003. URL: https://combinatorialpress.com/ars/vol68/

    2003

  15. [23]

    Dynamic coloring parameters for graphs with given genus

    Sarah Loeb, Thomas Mahoney, Benjamin Reiniger, and Jennifer Wise. Dynamic coloring parameters for graphs with given genus. Discrete Applied Mathematics , 235:129--141, 2018. https://doi.org/10.1016/j.dam.2017.09.013 doi:10.1016/j.dam.2017.09.013

    2018 doi

  16. [24]

    Ramanujan graphs

    Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica , 8(3):261--277, 1988. https://doi.org/10.1007/BF02126799 doi:10.1007/BF02126799

    1988 doi

  17. [25]

    Element deletion changes in dynamic coloring of graphs

    Lian-Ying Miao, Hong-Jian Lai, Yan-Fang Guo, and Zhengke Miao. Element deletion changes in dynamic coloring of graphs. Discrete Mathematics , 339(5):1600--1604, 2016. https://doi.org/10.1016/j.disc.2016.01.009 doi:10.1016/j.disc.2016.01.009

    2016 doi

  18. [26]

    Dynamic coloring of graphs

    Bruce Montgomery. Dynamic coloring of graphs . PhD dissertation, West Virginia University, 2001. https://doi.org/10.33915/etd.1397 doi:10.33915/etd.1397

    2001 doi

  19. [27]

    Grad and classes with bounded expansion I

    Jaroslav Ne s et r il and Patrice Ossona De Mendez. Grad and classes with bounded expansion I . D ecompositions. European Journal of Combinatorics , 29(3):760--776, 2008. https://doi.org/10.1016/j.ejc.2006.07.013 doi:10.1016/j.ejc.2006.07.013

    2008 doi

  20. [28]

    On nowhere dense graphs

    Jaroslav Ne s et r il and Patrice Ossona De Mendez. On nowhere dense graphs. European Journal of Combinatorics , 32(4):600--617, 2011. https://doi.org/10.1016/j.ejc.2011.01.006 doi:10.1016/j.ejc.2011.01.006

    2011 doi

  21. [29]

    Sparsity: G raphs, structures, and algorithms , volume 28

    Jaroslav Ne s et r il and Patrice Ossona De Mendez. Sparsity: G raphs, structures, and algorithms , volume 28. Springer Publishing Company, Incorporated, 2012. https://doi.org/10.1007/978-3-642-27875-4 doi:10.1007/978-3-642-27875-4

    2012 doi

  22. [30]

    Characterisations and examples of graph classes with bounded expansion

    Jaroslav Ne s et r il, Patrice Ossona de Mendez, and David R Wood. Characterisations and examples of graph classes with bounded expansion. European Journal of Combinatorics , 33(3):350--373, 2012. https://doi.org/10.1016/j.ejc.2011.09.008 doi:10.1016/j.ejc.2011.09.008

    2012 doi

  23. [31]

    From sparse graphs to nowhere dense structures: D ecompositions, independence, dualities and limits

    Jaroslav Ne s et r il and Patrice Ossona de Mendez. From sparse graphs to nowhere dense structures: D ecompositions, independence, dualities and limits. European Congress of Mathematics , 2010. https://doi.org/10.4171/077-1/7 doi:10.4171/077-1/7

    2010 doi

  24. [32]

    Arrangeability and clique subdivisions

    Vojt e ch R \"o dl and Robin Thomas. Arrangeability and clique subdivisions. In The Mathematics of Paul Erd o s II , pages 233--236. Springer, 2013. https://doi.org/10.1007/978-3-642-60406-5_20 doi:10.1007/978-3-642-60406-5_20

    2013 doi

  25. [33]

    Upper bounds of r-hued colorings of planar graphs

    Huimin Song and Hong-Jian Lai. Upper bounds of r-hued colorings of planar graphs. Discrete Applied Mathematics , 243:262--269, 2018. https://doi.org/10.1016/j.dam.2017.12.041 doi:10.1016/j.dam.2017.12.041

    2018 doi

  26. [34]

    Improper colourings inspired by H adwiger's conjecture

    Jan Van Den Heuvel and David R Wood. Improper colourings inspired by H adwiger's conjecture. arXiv preprint arXiv:1704.06536 , 2018. https://doi.org/10.48550/arXiv.1704.06536 doi:10.48550/arXiv.1704.06536

    2018 doi arXiv

  27. [35]

    Improper colourings inspired by H adwiger's conjecture

    Jan Van Den Heuvel and David R Wood. Improper colourings inspired by H adwiger's conjecture. Journal of the London Mathematical Society , 98(1):129--148, 2018. https://doi.org/10.1112/jlms.12127 doi:10.1112/jlms.12127

    2018 doi

  28. [36]

    Graphs with given diameter and a coloring problem

    Gerd Wegner. Graphs with given diameter and a coloring problem. Technical report, University of Dortmund, 1977

    1977

  29. [37]

    Colouring graphs with bounded generalized colouring number

    Xuding Zhu. Colouring graphs with bounded generalized colouring number. Discrete Mathematics , 309(18):5562--5568, 2009. https://doi.org/10.1016/j.disc.2008.03.024 doi:10.1016/j.disc.2008.03.024

    2009 doi

  30. [38]

    Édouard Bonnet, O joung Kwon, and David R. Wood. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond), 2022. URL: https://arxiv.org/abs/2202.11858, https://arxiv.org/abs/2202.11858 arXiv:2202.11858

    2022

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.