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.

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
• Title not available (Why is no real title available?)
• 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)