A stronger bound for the strong chromatic index

DOI10.1017/S0963548317000244zbMATH Open1378.05047arXiv1504.02583OpenAlexW2738901344MaRDI QIDQ4601050FDOQ4601050

Authors: Henning Bruhn, Felix Joos 

Publication date: 19 January 2018

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: We prove $ch{i_s}^{\prime }(G)leq1.93Delta(G{)}^2$ for graphs of sufficiently large maximum degree where $ch{i_s}^{\prime }(G)$ is the strong chromatic index of $G$. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where it is allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.

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

Recommendations

• A stronger bound for the strong chromatic index (extended abstract)
• A bound on the strong chromatic index of a graph
• An improved bound for the strong chromatic number
• On the Strong Chromatic Number of Graphs
• Publication:3201075

zbMATH Keywords

total colouringtotal chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• On Brooks' Theorem for Sparse Graphs
• Induced matchings in subcubic graphs
• A bound on the strong chromatic index of a graph
• Concentration of measure and isoperimetric inequalities in product spaces
• Weighted sums of certain dependent random variables
• Clique number of the square of a line graph
• Title not available (Why is that?)
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Induced matchings in bipartite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The strong chromatic index of a cubic graph is at most 10
• Counting cycles and finite dimensional \(L^{p}\) norms
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• Induced matchings in cubic graphs
• Coloring graphs with sparse neighborhoods
• Induced matchings in graphs of bounded maximum degree
• Concentration for Independent Permutations
• A Large Deviation Inequality for Functions of Independent, Multi-Way Choices
• The strong chromatic index ofC4-free graphs
• The distance-\(t\) chromatic index of graphs
• Concentration of multivariate polynomials and its applications
• A bound on the total chromatic number
• Title not available (Why is that?)
• On the method of typical bounded differences
• Induced matchings in graphs of degree at most 4

Cited In (33)

• A note on strong edge-coloring of claw-free cubic graphs
• \((1, 0)\)-relaxed strong edge list coloring of planar graphs with girth \(6\)
• Strong edge coloring of circle graphs
• A \((1,0)\)-relaxed strong list coloring of planar subcubic graphs
• The strong clique index of a graph with forbidden cycles
• An improved bound for the strong chromatic number
• Star edge-coloring of graphs with maximum degree four
• Colorings, transversals, and local sparsity
• Strong cliques and forbidden cycles
• A local epsilon version of Reed's conjecture
• Colouring graphs with forbidden bipartite subgraphs
• Strong edge coloring of subquartic graphs
• Strong cliques in claw-free graphs
• Title not available (Why is that?)
• Bounding the strong chromatic index of dense random graphs
• An asymptotic bound for the strong chromatic number
• A stronger bound for the strong chromatic index (extended abstract)
• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• Injective edge-coloring of subcubic graphs
• Revisiting semistrong edge‐coloring of graphs
• A special case of Vu's conjecture: colouring nearly disjoint graphs of bounded maximum degree
• Graph and hypergraph colouring via nibble methods: a survey
• Strong chromatic index of \(K_{1, t}\)-free graphs
• A proof of the Erdős-Faber-Lovász conjecture
• Colouring graphs with sparse neighbourhoods: bounds and applications
• On the list coloring version of Reed's conjecture
• Hypergraph incidence coloring
• Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree
• Strong edge-coloring of 2-degenerate graphs
• Strong chromatic index of graphs with maximum degree four
• A note on strong edge choosability of toroidal subcubic graphs
• Strong edge-colorings of sparse graphs with \(3\Delta-1\) colors
• Strong list-chromatic index of subcubic graphs

This page was built for publication: A stronger bound for the strong chromatic index

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