Strong chromatic index of subcubic planar multigraphs

DOI10.1016/J.EJC.2015.07.002MaRDI QIDQ499491zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 30 September 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

strong edge-coloringpolynomial time algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: The strong chromatic index of a multigraph is the minimum $k$ such that the edge set can be $k$-colored requiring that each color class induces a matching. We verify a conjecture of Faudree, Gy'{a}rf'{a}s, Schelp and Tuza, showing that every planar multigraph with maximum degree at most 3 has strong chromatic index at most 9, which is sharp.

Recommendations

• Strong edge-coloring of subcubic planar graphs
• scientific article; zbMATH DE number 1501957
• Strong list-chromatic index of subcubic graphs
• On the strong chromatic index of cyclic multigraphs

Cites work

• scientific article; zbMATH DE number 3882451 (Why is no real title available?)
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A bound on the strong chromatic index of a graph
• A stronger bound for the strong chromatic index (extended abstract)
• Induced matchings in cubic graphs
• Induced matchings in subcubic graphs
• Induced matchings in subcubic graphs without short cycles
• Induced matchings in subcubic planar graphs
• On Representatives of Subsets
• On induced matchings
• On strong edge-colouring of subcubic graphs
• Precise upper bound for the strong edge chromatic number of sparse planar graphs
• Problems and results in combinatorial analysis and graph theory
• Strong edge colouring of subcubic graphs
• Strong edge-coloring of planar graphs
• The strong chromatic index of a class of graphs
• The strong chromatic index of a cubic graph is at most 10

Cited in

(28)

• Strong edge-colorings of sparse graphs with large maximum degree
• Strong chromatic index in subset graphs
• A note on strong edge-coloring of claw-free cubic graphs
• Planar graphs with maximum degree 4 are strongly 19-edge-colorable
• Proper edge-colorings with a rich neighbor requirement
• Strong cliques in claw-free graphs
• Proof of a conjecture on the strong chromatic index of Halin graphs
• Every subcubic multigraph is (1,27) $(1,{2}^{7})$‐packing edge‐colorable
• scientific article; zbMATH DE number 1501957 (Why is no real title available?)
• Strong chromatic index and Hadwiger number
• Strong edge-coloring of pseudo-Halin graphs
• On the strong chromatic index of cyclic multigraphs
• The strong chromatic index of a cubic graph is at most 10
• Between Proper and Strong Edge-Colorings of Subcubic Graphs
• Strong edge-coloring of cubic bipartite graphs: a counterexample
• Strong chromatic index of \(K_{1, t}\)-free graphs
• Odd graph and its applications to the strong edge coloring
• From light edges to strong edge-colouring of 1-planar graphs
• Strong chromatic index of K₄-minor free graphs
• Between proper and strong edge‐colorings of subcubic graphs
• Recent progress on strong edge-coloring of graphs
• Strong edge-coloring for planar graphs with large girth
• On the strong chromatic index of sparse graphs
• Strong chromatic index of graphs with maximum degree four
• Strong edge colorings of graphs and the covers of Kneser graphs
• The tight bound for the strong chromatic indices of claw-free subcubic graphs
• Strong list-chromatic index of subcubic graphs
• Tree-like distance colouring for planar graphs of sufficient girth

This page was built for publication: Strong chromatic index of subcubic planar multigraphs

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