Strong edge-coloring of graphs with maximum degree 4 using 22 colors

DOI10.1016/J.DISC.2006.03.053MaRDI QIDQ2433734zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Daniel W. Cranston

Publication date 30 October 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0601623

zbMATH Keywords

edge-coloringstrong edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: In 1985, ErdH{o}s and Ne'{s}etril conjectured that the strong edge-coloring number of a graph is bounded above by $5/4Delt{a}^2$ when $Delta$ is even and $1/4(5Delt{a}^2-2Delta+1)$ when $Delta$ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for $Deltaleq3$. For $Delta=4$, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.

Review text

Erdős and Nesetril conjectured that every graph of even maximal degree \(\Delta\) can be strongly edge-colored by \(\frac54\Delta^2\) colors and if \(\Delta\) is odd by \(\frac14(5\Delta^2-2\Delta+1)\) colors. In this note the author gives a constructive contribution to the special case \(\Delta=4\).

Recommendations

• List strong edge-coloring of graphs with maximum degree 4
• Strong edge coloring sparse graphs
• Strong chromatic index of graphs with maximum degree four
• On strong edge-coloring of graphs with maximum degree 4
• Planar graphs with maximum degree 4 are strongly 19-edge-colorable

Cites work

• scientific article; zbMATH DE number 4177085 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• The strong chromatic index of a cubic graph is at most 10

Cited in

(56)

• The strong chromatic index of complete cubic Halin graphs
• On the precise value of the strong chromatic index of a planar graph with a large girth
• Strong chromatic index of graphs with maximum degree four
• On strong edge-coloring of graphs with maximum degree 4
• Upper bounds for the strong chromatic index of Halin graphs
• List strong edge coloring of planar graphs with maximum degree 4
• A note on strong edge coloring of sparse graphs
• Strong list-chromatic index of subcubic graphs
• Distance two edge labelings of lattices
• Proof of a conjecture on the strong chromatic index of Halin graphs
• Strong cliques in claw-free graphs
• Strong edge coloring of Cayley graphs and some product graphs
• List strong edge-coloring of graphs with maximum degree 4
• Odd graph and its applications to the strong edge coloring
• Strong edge-coloring of pseudo-Halin graphs
• Strong edge-colorings of sparse graphs with large maximum degree
• Strong chromatic index of K₄-minor free graphs
• On strong edge-colouring of subcubic graphs
• Strong edge-coloring for jellyfish graphs
• Strong chromatic index of sparse graphs
• Strong edge-coloring of subcubic planar graphs
• Squared chromatic number without claws or large cliques
• A stronger bound for the strong chromatic index (extended abstract)
• Strong edge coloring sparse graphs
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• On strong list edge coloring of subcubic graphs
• Strong edge-coloring for cubic Halin graphs
• scientific article; zbMATH DE number 1267271 (Why is no real title available?)
• A stronger bound for the strong chromatic index
• Strong chromatic index of planar graphs with large girth
• Strong edge-colorings for \(k\)-degenerate graphs
• A note on strong edge choosability of toroidal subcubic graphs
• Strong edge-coloring of \((3, \varDelta)\)-bipartite graphs
• t-strong cliques and the degree-diameter problem
• A \((1,0)\)-relaxed strong list coloring of planar subcubic graphs
• On \((s,t)\)-relaxed strong edge-coloring of graphs
• A note on the strong edge-coloring of outerplanar graphs with maximum degree 3
• Recent progress on strong edge-coloring of graphs
• Fractional strong chromatic index of bipartite graphs
• Induced matchings in graphs of degree at most 4
• The strong clique index of a graph with forbidden cycles
• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings
• The tight bound for the strong chromatic indices of claw-free subcubic graphs
• On strong edge-coloring of graphs with maximum degree 5
• Strong edge coloring of subquartic graphs
• \(t\)-strong cliques and the degree-diameter problem
• On strong chromatic index of some operations on graphs
• Strong chromatic index of graphs with small girth
• On strong incidence coloring of subcubic graphs
• Strong chromatic index of claw-free graphs with edge weight seven
• Every graph with maximum degree at most four is \((1^1,2^{19})\)-packing edge-colorable and \((1^2,2^{17})\)-packing edge-colorable
• Every cubic Halin graph is (1, 2⁶)-packing edge-colorable
• Strong edge chromatic index of subquartic graphs
• Strong chromatic index of \(K_{1, t}\)-free graphs
• The strong chromatic index of a class of graphs

This page was built for publication: Strong edge-coloring of graphs with maximum degree 4 using 22 colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433734)