On the strong chromatic index of sparse graphs

MaRDI QIDQ1658764zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1508.03515, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p18

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

zbMATH Keywords

sparse graphsstrong chromatic indexstrong edge coloring

Mathematics Subject Classification ID

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

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.

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

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 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
• A bound on the strong chromatic index of a graph
• A stronger bound for the strong chromatic index (extended abstract)
• An introduction to the discharging method via graph coloring
• Colorings and girth of oriented planar graphs
• Combinatorial Nullstellensatz
• Odd graph and its applications to the strong edge coloring
• 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 chromatic index of planar graphs with large girth
• Strong chromatic index of subcubic planar multigraphs
• Strong edge colouring of subcubic graphs
• Strong edge-coloring of planar graphs
• The Magma algebra system. I: The user language
• The incidence coloring conjecture for graphs of maximum degree 3
• The strong chromatic index of a class of graphs
• The strong chromatic index of a cubic graph is at most 10

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

Describes a project that uses

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)