pith. sign in

arxiv: 2210.05915 · v3 · submitted 2022-10-12 · 🧮 math.CO

Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)

Daniel W. Cranston This is my paper

Pith reviewed 2026-05-24 10:26 UTC · model grok-4.3

classification 🧮 math.CO
keywords graph coloringsquare of a graphlist coloringstrong edge-coloringplanar graphssparse graphspaint number
0
0 comments X

The pith

This survey collects known results on coloring the squares of planar and sparse graphs, including list and strong edge variants.

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

The paper surveys results on ordinary coloring, list coloring, and painting of the squares of graphs, with emphasis on strong edge-coloring. It concentrates on planar graphs and other sparse graph classes. A sympathetic reader would consult it to locate the current collection of bounds and open questions in these areas. The survey organizes the literature so that researchers can see which parameters are settled and which remain open for these distance-based coloring problems.

Core claim

The paper surveys the state of knowledge on coloring, list coloring, and painting the square of a graph, where the square G squared has an edge between any two vertices at distance one or two in G. Particular attention is given to strong edge-coloring, a variant in which edges at distance at most one must receive distinct colors. The focus remains on planar graphs and other sparse classes, compiling existing theorems and highlighting remaining questions.

What carries the argument

The square of a graph, the auxiliary graph obtained by adding edges between all pairs of vertices at distance at most two in the original graph; this construction converts distance constraints into ordinary adjacency so that standard coloring techniques apply directly.

If this is right

  • Known upper bounds on the chromatic number of squares of planar graphs with maximum degree Delta are collected and compared.
  • Results on the list chromatic number and paint number of these squares follow the same pattern as ordinary coloring in many sparse classes.
  • Strong edge-coloring of planar graphs reduces to coloring the square of the line graph under the appropriate distance metric.
  • Open questions listed in the survey indicate which sparsity conditions still lack tight bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The compiled bounds may supply explicit constants that can be fed into approximation algorithms for channel assignment on planar networks.
  • Techniques developed for planar squares could be tested for extension to graphs with bounded expansion or other sparsity measures.
  • The survey's organization by graph class suggests a template for future surveys on distance coloring in other hereditary classes.

Load-bearing premise

The surveyed literature is accurately and comprehensively represented without significant omissions or errors in summarizing prior results.

What would settle it

Discovery of a major published theorem on list coloring or strong edge-coloring of squares of planar graphs that is omitted or misstated in the survey.

Figures

Figures reproduced from arXiv: 2210.05915 by Daniel W. Cranston.

Figure 1
Figure 1. Figure 1: Graphs with ∆ = 4 and ∆ = 5 that have squares [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Diameter 2 planar graphs with maximum degrees 3, 4, 5, 7(6 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A planar graph Gs with ∆(Gs) = 2s and χ 2 (Gs) = ω 2 (Gs) = |V (Gs)| = 3s + 1. For planar G, with ∆ moderately small, the current best bound on χ 2 (G), is due to Molloy and Salavatipour [152]. Theorem 5 ([152]). If G is a planar graph, then χ 2 (G) 6  5 3∆  + 78. If also ∆ > 241, then χ 2 (G) 6  5 3∆  + 25. This result does not extend to χ 2 col(G) or even to χ 2 ℓ (G). However, asymptotically we can … view at source ↗
Figure 4
Figure 4. Figure 4: Left: A 4-coloring of G2 . Right: A 4-assignment L such that G2 admits no L-coloring. This example disproves Conjecture 7; see Theorem 8. It is difficult to prove general lower bounds on χ 2 (G) that are stronger than ∆ + 1. So most of the graphs for which Conjecture 7 has been proved are those for which χ 2 ℓ (G) = ∆ + 1. We discuss these in more detail in Section 3.2. However, in 2022 this conjecture was… view at source ↗
Figure 5
Figure 5. Figure 5: In any (D + 1)-coloring of the square of G′ D, the (D − 1)-vertex x and the 1-vertex z must receive distinct colors. Thus, χ(G2 D) > D + 2. Proposition 15 ([26, 71]). For every D > 3, there exists a planar graph GD with girth 6 and ∆ = D such that χ 2 (GD) = D + 2; see the right of [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Pairs (D, k), in columns, such that χ 2 ℓ (G) = ∆ + 1 if G is a planar graph with maximum degree ∆ > D and girth g > k. (The entry (−, 6) denotes that no such pair (D, 6) exists. References are in the preceeding few paragraphs.) In 2008, Dvoˇr´ak, Kr´al’, Nejedl´y, and Skrekovski [71] showed that for ˇ k = 6, the Wang–Lih Conjecture fails only by 1. Theorem 16 ([71]). If G is planar with girth at least 6 a… view at source ↗
Figure 7
Figure 7. Figure 7: Pairs (k, gk), in columns, such that χ 2 ℓ (G) 6 k if G is a planar graph with maximum degree ∆ = 3 and girth at least gk. (The entry (3, −) denotes that no such pair (3, g3) exists. References are in the preceeding few paragraphs.) Let G be a planar graph with ∆ = 3 and girth g. Cranston and Kim [61] showed that χ 2 ℓ (G) 6 7 if g > 7. Dvoˇr´ak, Skrekovski, and Tancer [72] showed that (i) ˇ χ 2 ℓ (G) 6 6 … view at source ↗
Figure 8
Figure 8. Figure 8: Triples (D, k, C) such that every graph G with ∆(G) > D and mad(G) < k satisfy χ 2 ℓ (G) 6 C. References appear below (and near the end of the section). whenever ∆ > 5 and mad(G) < 2 + 4∆−8 5∆+2 . In particular, this includes all planar graphs with girth at least 7 + 12 ∆−2 . Hence, it proves the analogue of Conjecture 13 for g > 8. The case g > 7 was subsumed by Bonamy, L´evˆeque, and Pinlou [18] and stre… view at source ↗
Figure 9
Figure 9. Figure 9: A graph GC,D with ∆(GC,D) = D + 1 and χ 2 (GC,D) > ∆(GC,D) + C + 1 and mad(GC,D) < 4 − 2 C+1 , as in Theorem 22. towards wj and the rest towards zij . Orient vix towards vi and orient wjy towards wj . Orient xy arbitrarily. This orientation has maximum indegree 2− 1 C+1 , which proves that mad(GC,D) 6 2(2 − 1 C+1 ). Showing the inequality is strict requires a few more details, which we omit. Bonamy, L´evˆe… view at source ↗
Figure 10
Figure 10. Figure 10: The graph GD in Theorem 23. In G2 D, the black vertices form a clique of order 5D/2. Theorem 23 ([96]). For each positive even integer D, there exists a 2-degenerate graph GD, with mad(GD) < 4, maximum degree D, and χ 2 (GD) > 5D 2 . (See [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Graphs illustrating that each part of Conjecture 31 is be [PITH_FULL_IMAGE:figures/full_fig_p022_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Figures (a), (b), and (c) illustrate, respectively, that [PITH_FULL_IMAGE:figures/full_fig_p024_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Left: Triples (g, D, f(∆)), in columns, such that every planar graph G with girth at least g and ∆(G) > D satisfies χ s (G) 6 f(∆). Right: Triples (k, D, f(∆)) such that every graph G with mad(G) < k and ∆(G) > D satisfies χ s (G) 6 f(∆). References for both tables appear throughout Section 4.3. 5 Odds and Ends In this section we briefly touch on a few more related problems. 5.1 Total Coloring and List Co… view at source ↗
read the original abstract

We survey work on coloring, list coloring, and painting squares of graphs; in particular, we consider strong edge-coloring. We focus primarily on planar graphs and other sparse classes of graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper surveys results on vertex coloring, list coloring, and painting of the square of a graph G^2, with particular attention to strong edge-coloring (which is equivalent to coloring the square of the line graph). The focus is on planar graphs and other sparse classes such as graphs with bounded maximum average degree, and the survey collects known bounds, conjectures, and partial results without proving new theorems.

Significance. A well-executed survey in this area would be useful to the community by organizing the many incremental results on square coloring parameters for planar and sparse graphs, identifying which conjectures remain open, and pointing to techniques that have been successful. The absence of new theorems is appropriate for the survey format.

minor comments (1)
  1. The abstract and title mention 'other related problems' but the scope of these problems is not delineated in the provided front matter; a brief clarifying sentence would help readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of our survey and for recommending acceptance. The report accurately captures the scope and purpose of the manuscript as a compilation of existing results on coloring squares of graphs, with emphasis on planar and sparse classes, without introducing new theorems.

Circularity Check

0 steps flagged

Survey paper with no derivations or predictions

full rationale

This is explicitly a survey paper whose abstract and content state that it reviews existing literature on coloring squares of graphs, with no new theorems, proofs, equations, fitted parameters, or predictions introduced by the author. No derivation chain exists to inspect for circularity. The load-bearing content is faithful representation of prior results, which is an external accuracy issue rather than internal circularity. Per the rules, a self-contained review against external benchmarks receives score 0 with empty steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a survey paper with no new mathematical derivations, free parameters, axioms, or invented entities introduced by the authors.

pith-pipeline@v0.9.0 · 5537 in / 951 out tokens · 22786 ms · 2026-05-24T10:26:52.213818+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

198 extracted references · 198 canonical work pages · 39 internal anchors

  1. [1]

    ´Editions du Centre National de la Recherche Scientifique (CNRS), Paris, 1978

    Probl` emes combinatoires et th´ eorie des graphes, volume 260 of Colloques Internationaux du Centre National de la Recherche Scientifique [International Collo quia of the CNRS] . ´Editions du Centre National de la Recherche Scientifique (CNRS), Paris, 1978. Colloque International CNRS held at the Universit´ e d’Orsay, Orsay, July 9–13, 1976. 26

    work page 1978

  2. [2]

    Agnarsson and M

    G. Agnarsson and M. M. Halld´ orsson. Coloring powers of planar g raphs. SIAM J. Discrete Math. , 16(4):651–662 (electronic), 2003. 11, 30

    work page 2003

  3. [3]

    N. Alon. Restricted colorings of graphs. In Surveys in combinatorics, 1993 (Keele) , volume 187 of London Math. Soc. Lecture Note Ser. , pages 1–33. Cambridge Univ. Press, Cambridge, 1993. 26

    work page 1993

  4. [4]

    N. Alon, M. Krivelevich, and B. Sudakov. Coloring graphs with spar se neighborhoods. J. Combin. Theory Ser. B , 77(1):73–82, 1999. 31

    work page 1999

  5. [5]

    Alon and B

    N. Alon and B. Mohar. The chromatic number of graph powers. Combin. Probab. Comput. , 11(1):1–10, 2002. http://www.imfm.si/preprinti/PDF/00719.pdf. 30

    work page 2002

  6. [6]

    Alon and M

    N. Alon and M. Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125–134, 1992. 3

    work page 1992

  7. [7]

    A Unified Approach to Distance-Two Colouring of Graphs on Surfaces

    O. Amini, L. Esperet, and J. Van Den Heuvel. A unified approach to distance-two colouring of graphs on surfaces. Combinatorica, 33(3):253–296, 2013, arXiv:0812.1345. 8

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  8. [8]

    Andersen

    L. Andersen. Total colouring of simple graphs. Master’s thesis, University of Aalborg, the Nether- lands, 1993. 26, 27

    work page 1993

  9. [9]

    L. D. Andersen. The strong chromatic index of a cubic graph is at most 10. Discrete Math. , 108(1-3):231–252, 1992. Topological, algebraical and combinator ial structures. Frol ´ ık’s memorial volume. 19, 21

    work page 1992

  10. [10]

    R. C. Baker, G. Harman, and J. Pintz. The difference between c onsecutive primes. II. Proc. London Math. Soc. (3) , 83(3):532–562, 2001. 6

    work page 2001

  11. [11]

    Bannai and T

    E. Bannai and T. Ito. On finite Moore graphs. J. Fac. Sci. Univ. Tokyo Sect. IA Math. , 20:191–208,

    work page

  12. [12]

    M. Behzad. Graphs and Their Chromatic Numbers . ProQuest LLC, Ann Arbor, MI, 1965. Thesis (Ph.D.)–Michigan State University. 25

    work page 1965

  13. [13]

    Bensmail, M

    J. Bensmail, M. Bonamy, and H. Hocquard. Strong edge coloring sparse graphs. Electronic Notes in Discrete Mathematics (Proceedings of Eurocomb 2015) , 49:773–778, 2015. 23 the electronic journal of combinatorics 30(2) (2023), #DS25 33

    work page 2015

  14. [14]

    Strong edge-colouring of sparse planar graphs

    J. Bensmail, A. Harutyunyan, H. Hocquard, and P. Valicov. Str ong edge-colouring of sparse planar graphs. Discrete Appl. Math. , 179:229–234, 2014, arXiv:1401.4568. 23

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  15. [15]

    Bollob´ as

    B. Bollob´ as. Extremal graph theory , volume 11 of London Mathematical Society Monographs . Aca- demic Press, Inc. [Harcourt Brace Jovanovich, Publishers], Londo n-New York, 1978. 30

    work page 1978

  16. [16]

    Brooks' theorem on powers of graphs

    M. Bonamy and N. Bousquet. Brooks’ theorem on powers of gr aphs. Discrete Math. , 325:12–16, 2014, arXiv:1310.5493. 29

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  17. [17]

    Bonamy, D

    M. Bonamy, D. W. Cranston, and L. Postle. Planar graphs of gir th at least five are square (∆ + 2)- choosable. J. Combin. Theory Ser. B , 134:218–238, 2019, arXiv:1508.03663. 13

    work page arXiv 2019

  18. [18]

    Bonamy, B

    M. Bonamy, B. L´ evˆ eque, and A. Pinlou. 2-distance coloring of sparse graphs. J. Graph Theory , 77(3):190–218, 2014. 16, 17, 27

    work page 2014

  19. [19]

    Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable

    M. Bonamy, B. L´ evˆ eque, and A. Pinlou. Graphs with maximum de gree ∆ ⩾ 17 and maximum average degree less than 3 are list 2-distance (∆ + 2)-colorable. Discrete Math. , 317:19–32, 2014, arXiv:1301.7090. 16

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  20. [20]

    List coloring the square of sparse graphs with large degree

    M. Bonamy, B. L´ evˆ eque, and A. Pinlou. List coloring the square of sparse graphs with large degree. European J. Combin. , 41:128–137, 2014, arXiv:1308.4197. 16, 17, 27

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  21. [21]

    Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications

    M. Bonamy, T. Perrett, and L. Postle. Colouring graphs with sp arse neighbourhoods: bounds and applications. J. Combin. Theory Ser. B , 155:278–317, 2022, arXiv:1810.06704. 20, 21

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  22. [22]

    J. A. Bondy and U. S. R. Murty. Graph theory , volume 244 of Graduate Texts in Mathematics . Springer, New York, 2008. https://doi.org/10.1007/978-1-84628-970-5. 2

    work page doi:10.1007/978-1-84628-970-5 2008

  23. [23]

    O. V. Borodin. On the total coloring of planar graphs. J. Reine Angew. Math. , 394:180–185, 1989. 27

    work page 1989

  24. [24]

    O. V. Borodin, H. J. Broersma, A. Glebov, and J. van den Heuve l. Stars and bunches in planar graphs, Part I: Triangulations. CDAM Research Report Series , 2002–04, 2002. http://www.cdam.lse.ac.uk/Reports/Abstracts/cdam-20 02-04.html. Original Russian ver- sion. Diskretn. Anal. Issled. Oper. Ser. 1 8 (2001), no. 2, 15–39. 11

    work page 2002

  25. [25]

    O. V. Borodin, H. J. Broersma, A. Glebov, and J. van den Heuve l. Stars and bunches in planar graphs, Part II: General planar graphs and colourings. CDAM Research Report Series , 2002–05,

    work page 2002

  26. [26]

    Original Russian version

    http://www.cdam.lse.ac.uk/Reports/Abstracts/cdam-20 02-05.html. Original Russian version. Diskretn. Anal. Issled. Oper. Ser. 1 8 (2001), no. 4, 9–33. 11

    work page 2001

  27. [27]

    O. V. Borodin, A. N. Glebov, A. O. Ivanova, T. K. Neustroeva, and V. A. Tashkinov. Sufficient conditions for planar graphs to be 2-distance (∆ + 1)-colorable. Sib. `Elektron. Mat. Izv. , 1:129–141,

    work page

  28. [28]

    O. V. Borodin and A. O. Ivanova. 2-distance (∆ + 2)-coloring of planar graphs with girth six and ∆ ⩾ 18. Discrete Math., 309(23-24):6496–6502, 2009. 13

    work page 2009

  29. [29]

    O. V. Borodin and A. O. Ivanova. List 2-distance (∆ + 2)-colorin g of planar graphs with girth six. European J. Combin. , 30(5):1257–1262, 2009. 13

    work page 2009

  30. [30]

    O. V. Borodin and A. O. Ivanova. List 2-distance (∆ + 2)-colorin g of planar graphs with girth six and ∆ ⩾ 24. Sibirsk. Mat. Zh. , 50(6):1216–1224, 2009. translation in Sib. Math. J. 50 (2009), no. 6, 958–964. 13

    work page 2009

  31. [31]

    O. V. Borodin and A. O. Ivanova. 2-distance 4-coloring of plana r subcubic graphs. Diskretn. Anal. Issled. Oper., 18(2):18–28, 98, 2011. 15

    work page 2011

  32. [32]

    O. V. Borodin and A. O. Ivanova. 2-distance 4-colorability of pla nar subcubic graphs with girth at least 22. Discuss. Math. Graph Theory , 32(1):141–151, 2012. 15

    work page 2012

  33. [33]

    O. V. Borodin and A. O. Ivanova. Precise upper bound for the s trong edge chromatic number of sparse planar graphs. Discuss. Math. Graph Theory , 33(4):759–770, 2013. 24

    work page 2013

  34. [34]

    O. V. Borodin, A. O. Ivanova, and T. K. Neustroeva. 2-distan ce coloring of sparse planar graphs. Sib. `Elektron. Mat. Izv. , 1:76–90, 2004. 13 the electronic journal of combinatorics 30(2) (2023), #DS25 34

    work page 2004

  35. [35]

    O. V. Borodin, A. O. Ivanova, and T. K. Neustroeva. A prescr ibed 2-distance (∆ + 1)-coloring of planar graphs with a given girth. Diskretn. Anal. Issled. Oper. Ser. 1 , 14(3):13–30, 2007. 13, 14, 27

    work page 2007

  36. [36]

    O. V. Borodin and A. V. Kostochka. On an upper bound of a grap h’s chromatic number, depending on the graph’s degree and density. J. Comb. Theory, B , 23(2-3):247–250, 1977. 7

    work page 1977

  37. [37]

    O. V. Borodin, A. V. Kostochka, and D. R. Woodall. List edge and list total colourings of multi- graphs. J. Combin. Theory Ser. B , 71(2):184–204, 1997. 28

    work page 1997

  38. [38]

    O. V. Borodin, A. V. Kostochka, and D. R. Woodall. Total colorin gs of planar graphs with large maximum degree. J. Graph Theory , 26(1):53–59, 1997. 27

    work page 1997

  39. [39]

    O. V. Borodin, A. V. Kostochka, and D. R. Woodall. Total colour ings of planar graphs with large girth. European J. Combin. , 19(1):19–24, 1998. 27

    work page 1998

  40. [40]

    Bousquet, Q

    N. Bousquet, Q. Deschamps, L. de Meyer, and T. Pierron. Imp roved square coloring of planar graphs. 2021, arXiv:2112.12512. 11

    work page arXiv 2021

  41. [41]

    W. G. Brown. On graphs that do not contain a Thompsen graph. Canad. Math. Bull. , 9:281–285,

    work page

  42. [42]

    R. A. Brualdi and J. J. Q. Massey. Incidence and strong edge c olorings of graphs. Discrete Math., 122(1-3):51–58, 1993. 19

    work page 1993

  43. [43]

    A stronger bound for the strong chromatic index

    H. Bruhn and F. Joos. A stronger bound for the strong chrom atic index. Combin. Probab. Comput., 27(1):21–43, 2018, arXiv:1504.02583. 20, 21

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  44. [44]

    Calamoneri

    T. Calamoneri. The l(h,k)-labelling problem: An updated survey an d annotated bibliography. Comput. J. , 54:1344–1371, 2011. 29

    work page 2011

  45. [45]

    Cambie, W

    S. Cambie, W. Cames van Batenburg, R. de Joannis de Verclos, a nd R. J. Kang. Maximizing line subgraphs of diameter at most t. SIAM J. Discrete Math. , 36(2):939–950, 2022, arXiv:2103.11898. 30

    work page arXiv 2022

  46. [46]

    E. A. Canale and J. G´ omez. Asymptotically large (∆ , D)-graphs. Discrete Appl. Math. , 152(1- 3):89–108, 2005. 30

    work page 2005

  47. [47]

    G. J. Chang and D. Kuo. The L(2, 1)-labeling problem on graphs. SIAM J. Discrete Math. , 9(2):309–316, 1996. 28

    work page 1996

  48. [48]

    G. J. Chang, M. Montassier, A. Pˆ echer, and A. Raspaud. Str ong chromatic index of planar graphs with large girth. Discuss. Math. Graph Theory , 34(4):723–733, 2014. 24

    work page 2014

  49. [49]

    Chang, J.-L

    J. Chang, J.-L. Wu, and Y.-G. A. Total colorings of planar graph s with sparse triangles. Theoret. Comput. Sci. , 526:120–129, 2014. 27

    work page 2014

  50. [50]

    Charpentier

    C. Charpentier. 2-distance coloring of not-so-sparse graph s. 2014. www.labri.fr/perso/charpent/2dcol-not-so-sparse.pdf . 16, 17

    work page 2014

  51. [51]

    Chen and J

    D. Chen and J. Wu. The total coloring of some graphs. In Combinatorics, Graph Theory, Al- gorithms, and Applications, Beijing, 1993 , pages 17–20. World Scientific, River Edge, NY, 1994. 27

    work page 1993

  52. [52]

    L. Chen, K. Deng, G. Yu, and X. Zhou. Strong edge-coloring fo r planar graphs with large girth. Discrete Math., 342(2):339–343, 2019. 25

    work page 2019

  53. [53]

    Chetwynd and R

    A. Chetwynd and R. H¨ aggkvist. An improvement of Hind’s upper bound on the total chromatic number. Combin. Probab. Comput. , 5(2):99–104, 1996. 26

    work page 1996

  54. [54]

    I. Choi, D. W. Cranston, and T. Pierron. Degeneracy and color ings of squares of planar graphs without 4-cycles. Combinatorica, 40(5):625–653, 2020, arXiv:1806.07204. 14

    work page arXiv 2020

  55. [55]

    I. Choi, J. Kim, A. V. Kostochka, and A. Raspaud. Strong edge -colorings of sparse graphs with large maximum degree. European J. Combin. , 67:21–39, 2018, arXiv:1610.05406. 23, 24 the electronic journal of combinatorics 30(2) (2023), #DS25 35

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  56. [56]

    F. R. K. Chung, A. Gy´ arf´ as, Z. Tuza, and W. T. Trotter. Th e maximum number of edges in 2K2-free graphs of bounded degree. Discrete Math., 81(2):129–135, 1990. 19

    work page 1990

  57. [57]

    Conde and J

    J. Conde and J. Gimbert. On the existence of graphs of diamete r two and defect two. Discrete Math., 309(10):3166–3172, 2009. 6

    work page 2009

  58. [58]

    D. W. Cranston. Strong edge-coloring of graphs with maximum d egree 4 using 22 colors. Discrete Math., 306(21):2772–2778, 2006, arXiv:math/0601623. 19

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  59. [59]

    D. W. Cranston. Strong edge-coloring of cubic bipartite graph s: a counterexample. Discrete Appl. Math., 321:258–260, 2022, arXiv:2112.01443. 22

    work page arXiv 2022

  60. [60]

    D. W. Cranston, R. Erman, and R. ˇSkrekovski. Choosability of the square of a planar graph with maximum degree four. Australas. J. Combin. , 59:86–97, 2014, arXiv:1303.5156. 15

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  61. [61]

    D. W. Cranston and B. Jaeger. List-coloring the squares of pla nar graphs without 4-cycles and 5-cycles. J. Graph Theory , 85(4):721–737, 2017, arXiv:1505.03197. 14

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  62. [62]

    D. W. Cranston and S.-J. Kim. List-coloring the square of a subc ubic graph. J. Graph Theory , 57(1):65–87, 2008, arXiv:1503.00157. 2, 5, 14

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  63. [63]

    D. W. Cranston and L. Rabern. Painting squares in ∆ 2− 1 shades. Electron. J. Combin., 23(2):Paper 2.50, 30, 2016, arXiv:1311.1251. 5, 14, 15

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  64. [64]

    D. W. Cranston and R. ˇSkrekovski. Sufficient sparseness conditions for G2 to be (∆ + 1)-choosable, when ∆ ⩾ 5. Discrete Appl. Math. , 162:167–176, 2014, arXiv:1303.5136. 15, 27

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  65. [65]

    D. W. Cranston and D. B. West. An introduction to the discharg ing method via graph coloring. Discrete Math., 340(4):766–793, 2017, arXiv:1306.4434. 2, 11, 15, 23, 28

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  66. [66]

    R. M. Damerell. On Moore graphs. Proc. Cambridge Philos. Soc. , 74:227–236, 1973. 29

    work page 1973

  67. [67]

    Davies, R

    E. Davies, R. J. Kang, F. Pirot, and J.-S. Sereni. Graph struct ure via local occupancy. 2020, arXiv:2003.14361. 20

    work page arXiv 2020

  68. [68]

    R. Diestel. Graph Theory. Springer-Verlag, Heidelberg, 4th edition, 2010. 2

    work page 2010

  69. [69]

    M. H. Dolama and E. Sopena. On the maximum average degree and the incidence chromatic number of a graph. Discrete Math. and Theoret. Comput. Sci. , 7(1):203–216, 2005. 15

    work page 2005

  70. [70]

    Dong and B

    W. Dong and B. Xu. 2-distance coloring of planar graphs without 4-cycles and 5-cycles. SIAM J. Discrete Math., 33(3):1297–1312, 2019. 14

    work page 2019

  71. [71]

    Duraj, G

    L. Duraj, G. Gutowski, and J. Kozik. Chip games and paintability. Electron. J. Combin. , 23(3):Pa- per 3.3, 12, 2016, arXiv:1506.01148. 3

    work page arXiv 2016

  72. [72]

    Dvoˇ r´ ak, D

    Z. Dvoˇ r´ ak, D. Kr´ a ’l, P. Nejedl´ y, and R. ˇSkrekovski. Coloring squares of planar graphs with girth six. European J. Combin. , 29(4):838–849, 2008. http://kam.mff.cuni.cz/~kamserie/serie/clanky/2005/s727.ps. 12, 13

    work page 2008

  73. [73]

    Dvoˇ r´ ak, R

    Z. Dvoˇ r´ ak, R. ˇSkrekovski, and M. Tancer. List-coloring squares of sparse subcubic graphs. SIAM J. Discrete Math. , 22(1):139–159, 2008. http://kam.mff.cuni.cz/~kamserie/serie/clanky/2005/s734.ps. 14, 27

    work page 2008

  74. [74]

    B. Elspas. Topological constraints on interconnection-limited lo gic. Proc. IEEE Fifth Symposium on Switching Circuit Theory and Logical Design, IEEE S-164 , pages 133–147, 1964. 5, 6

    work page 1964

  75. [75]

    P. Erd˝ os. Problems and results in combinatorial analysis and gr aph theory. In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986) , volume 72, pages 81–92, 1988. https://doi.org/10.1016/0012-365X(88)90196-3. 30

    work page doi:10.1016/0012-365x(88)90196-3 1986

  76. [76]

    Erd˝ os, A

    P. Erd˝ os, A. L. Rubin, and H. Taylor. Choosability in graphs. In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (H umboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pages 125–157. Utilitas Math., Winnipeg, Man., 1980. 3, 6

    work page 1979

  77. [77]

    Erd˝ os, S

    P. Erd˝ os, S. Fajtlowicz, and A. Hoffman. Maximum degree in gra phs of diameter 2. Networks, 10(1):87–90, 1980. 5 the electronic journal of combinatorics 30(2) (2023), #DS25 36

    work page 1980

  78. [78]

    Acyclic edge-coloring using entropy compression

    L. Esperet and A. Parreau. Acyclic edge-coloring using entrop y compression. European J. Combin., 34(6):1019–1027, 2013, arXiv:1206.1535. 2

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  79. [79]

    V. Faber. Existence of a Moore graph of degree 57 is still open. 2022, arXiv:2210.09577. 5

    work page arXiv 2022

  80. [80]

    On the clique number of the square of a line graph and its relation to Ore-degree

    M. Faron and L. Postle. On the clique number of the square of a lin e graph and its relation to maximum degree of the line graph. J. Graph Theory , 92(3):261–274, 2019, arXiv:1708.02264. 19

    work page internal anchor Pith review Pith/arXiv arXiv 2019

Showing first 80 references.