On the strong chromatic index of sparse graphs

zbMATH Open1393.05112arXiv1508.03515MaRDI QIDQ1658764FDOQ1658764

Authors: Philip Deorsey, Michael Ferrara, Nathan Graber, Stephen G. Hartke, Luke L. Nelsen, Sogol Jahanbekam, Bernard Lidický, Derrick Stolee, Jennifer White, Eric C. Sullivan 

Publication date: 15 August 2018

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The strong chromatic index of a graph $G$, denoted $ch{i_s}^{\prime }(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $ch{i}_{s^{\prime },ell}(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $operatornamegirth(G)geq41$ then $ch{i}_{s^{\prime },ell}(G)leq5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $operatornamegirth(G)geq30$, then $ch{i_s}^{\prime }(G)leq5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $operatornamegirth(G)geq28$, then $ch{i_s}^{\prime }(G)leq7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Strong list-chromatic index of subcubic graphs
• Strong edge-coloring of subcubic planar graphs
• On the precise value of the strong chromatic index of a planar graph with a large girth
• Precise upper bound for the strong edge chromatic number of sparse planar graphs
• Strong edge-coloring of planar graphs

zbMATH Keywords

sparse graphsstrong chromatic indexstrong edge coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Cites Work

• The Magma algebra system. I: The user language
• Title not available (Why is that?)
• A bound on the strong chromatic index of a graph
• Title not available (Why is that?)
• Colorings and girth of oriented planar graphs
• Combinatorial Nullstellensatz
• Problems and results in combinatorial analysis and graph theory
• The strong chromatic index of a cubic graph is at most 10
• The incidence coloring conjecture for graphs of maximum degree 3
• On induced matchings
• The strong chromatic index of a class of graphs
• A stronger bound for the strong chromatic index (extended abstract)
• Title not available (Why is that?)
• On strong edge-colouring of subcubic graphs
• Strong edge colouring of subcubic graphs
• Title not available (Why is that?)
• Strong chromatic index of planar graphs with large girth
• Precise upper bound for the strong edge chromatic number of sparse planar graphs
• Strong edge-coloring of planar graphs
• Strong chromatic index of subcubic planar multigraphs
• An introduction to the discharging method via graph coloring
• A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
• Odd graph and its applications to the strong edge coloring

Cited In (9)

• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• The strong chromatic index of sparse graphs
• Precise upper bound for the strong edge chromatic number of sparse planar graphs
• Odd graph and its applications to the strong edge coloring
• On strong edge-coloring of graphs with maximum degree 4
• Upper bounds for the strong chromatic index of Halin graphs
• Recent progress on strong edge-coloring of graphs
• Strong edge colorings of graphs and the covers of Kneser graphs
• Strong list-chromatic index of subcubic graphs

Uses Software

• Magma

This page was built for publication: On the strong chromatic index of sparse graphs

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