Odd graph and its applications to the strong edge coloring

DOI10.1016/J.AMC.2017.11.057zbMATH Open1428.05120arXiv1412.8358OpenAlexW2768840597MaRDI QIDQ2279245FDOQ2279245

Authors: Tao Wang, Xiaodan Zhao 

Publication date: 12 December 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: A strong edge coloring of a graph is a proper edge coloring in which every color class is an induced matching. The strong chromatic index $ch{i_s}^{\prime }(G)$ of a graph $G$ is the minimum number of colors in a strong edge coloring of $G$. Let $Deltageq4$ be an integer. In this note, we study the odd graphs and show the existence of some special walks. By using these results and Chang's ideas in [Discuss. Math. Graph Theory 34 (4) (2014) 723--733], we show that every planar graph with maximum degree at most $Delta$ and girth at least $10Delta-4$ has a strong edge coloring with $2Delta-1$ colors. In addition, we prove that if $G$ is a graph with girth at least $2Delta-1$ and mad$(G)<2+frac13Delta-2$, where $Delta$ is the maximum degree and $Deltageq4$, then $ch{i_s}^{\prime }(G)leq2Delta-1$, if $G$ is a subcubic graph with girth at least $8$ and mad$(G)<2+frac223$, then $ch{i_s}^{\prime }(G)leq5$.

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

Recommendations

• Odd edge coloring of graphs
• A note on weak odd edge-colorings of graphs
• Strong edge colorings of graphs
• Odd properly colored cycles in edge-colored graphs
• Remarks on odd colorings of graphs
• scientific article; zbMATH DE number 3851125
• Parity and strong parity edge-colorings of graphs
• scientific article; zbMATH DE number 5237271
• Odd edge‐colorings of subdivisions of odd graphs
• scientific article; zbMATH DE number 7666240

zbMATH Keywords

planar graphsstrong chromatic indexmaximum average degreestrong edge coloringodd graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• A bound on the strong chromatic index of a graph
• Title not available (Why is that?)
• Colorings and girth of oriented planar graphs
• Problems and results in combinatorial analysis and graph theory
• The strong chromatic index of a cubic graph is at most 10
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• Induced matchings in cubic graphs
• Title not available (Why is that?)
• 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
• On the strong chromatic index of sparse graphs
• Strong chromatic index of subcubic planar multigraphs
• An introduction to the discharging method via graph coloring

Cited In (8)

• The strong chromatic index of graphs with restricted Ore-degrees.
• Odd edge-colorability of subcubic graphs
• Weak-odd edge-coloring of digraphs
• On the precise value of the strong chromatic index of a planar graph with a large girth
• Structure and Coloring of Graphs with Only Small Odd Cycles
• Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation
• Recent progress on strong edge-coloring of graphs
• On the strong chromatic index of sparse graphs

This page was built for publication: Odd graph and its applications to the strong edge coloring

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