The strong chromatic index of graphs and subdivisions

DOI10.1016/J.IPL.2016.08.007zbMATH Open1388.05179arXiv1506.03913OpenAlexW2963537481MaRDI QIDQ318921FDOQ318921

Kittikorn Nakprasit, Keaitsuda Nakprasit

Publication date: 6 October 2016

Published in: Information Processing Letters, Discrete Mathematics (Search for Journal in Brave)

Abstract: A $(q,r)$emph{-tree-coloring} of a graph $G$ is a $q$-coloring of vertices of $G$ such that the subgraph induced by each color class is a forest of maximum degree at most $r.$ An emph{equitable $(q,r)$-tree-coloring} of a graph $G$ is a $(q,r)$-tree-coloring such that the sizes of any two color classes differ by at most one. Let the emph{strong equitable vertex $r$-arboricity} be the minimum $p$ such that $G$ has an equitable $(q,r)$-tree-coloring for every $qgeqp.$ In this paper, we find the exact value for each $v{a}^{e}qui{v}_2(K_{m,n})$ and $v{a}^{e}qui{v}_2(K_{l,m,n}).$

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

Recommendations

• Strong chromatic index of subcubic planar multigraphs
• scientific article; zbMATH DE number 1501957
• On the strong chromatic index of cyclic multigraphs
• The strong chromatic index of a class of graphs
• A bound on the strong chromatic index of a graph

zbMATH Keywords

graph algorithmscombinatorial problemsstrong chromatic indexsubdivisionincidence coloringcomplete bipartite graphscomplete tripartite graphsstrong edge-coloringvertex \(k\)-arboricity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Title not available (Why is that?)
• Equitable vertex arboricity of graphs
• Incidence and strong edge colorings of graphs
• Induced matchings in bipartite graphs
• Equitable coloring and the maximum degree
• The strong chromatic index of a cubic graph is at most 10
• Equitable colorings of outerplanar graphs
• On equitable coloring of bipartite graphs
• Equitable colorings of planar graphs without short cycles
• A note on relaxed equitable coloring of graphs
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• Strong chromatic index in subset graphs
• The strong chromatic index of graphs with restricted Ore-degrees.
• Strong chromatic index of subset graphs
• Title not available (Why is that?)
• Equitable \(\Delta\)-coloring of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equitable Coloring
• Induced matchings in cubic graphs
• The equitable vertex arboricity of complete tripartite graphs
• On equitable and equitable list colorings of series-parallel graphs
• On induced matchings
• Equitable colorings of planar graphs with maximum degree at least nine
• A note on the strong chromatic index of bipartite graphs
• Equitable list colorings of planar graphs without short cycles
• The strong chromatic index of a class of graphs
• Equitable list coloring of planar graphs without 4- and 6-cycles

Cited In (9)

• On incidence choosability of cubic graphs
• The strong chromatic index of sparse graphs
• A stronger bound for the strong chromatic index (extended abstract)
• On the strong chromatic index of cyclic multigraphs
• Strong edge chromatic index of the generalized Petersen graphs
• On the complexity of the flow coloring problem
• Strong chromatic index of subcubic planar multigraphs
• Strong chromatic index in subset graphs
• Fractional strong chromatic index of bipartite graphs

This page was built for publication: The strong chromatic index of graphs and subdivisions

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