A stronger bound for the strong chromatic index

DOI10.1017/S0963548317000244MaRDI QIDQ4601050zbMATH OpenOpenAlexFDO

Authors Henning Bruhn, Felix Joos

Publication date 19 January 2018

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

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

zbMATH Keywords

total colouringtotal chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

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

Cited in

(33)

• Strong edge coloring of circle graphs
• \((1, 0)\)-relaxed strong edge list coloring of planar graphs with girth \(6\)
• A note on strong edge-coloring of claw-free cubic 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
• Bounding the strong chromatic index of dense random graphs
• scientific article; zbMATH DE number 1836093 (Why is no real title available?)
• A stronger bound for the strong chromatic index (extended abstract)
• An asymptotic bound for the strong chromatic number
• 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
• On the list coloring version of Reed's conjecture
• Colouring graphs with sparse neighbourhoods: bounds and applications
• Hypergraph incidence coloring
• Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree
• Strong chromatic index of graphs with maximum degree four
• Strong edge-coloring of 2-degenerate graphs
• 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)