Vertex colouring edge partitions

DOI10.1016/J.JCTB.2005.01.001MaRDI QIDQ2485946zbMATH OpenOpenAlexFDO

Authors Louigi Addario-Berry, Ketan Dalal, R. E. L. Aldred, Bruce Reed

Publication date 5 August 2005

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2005.01.001

zbMATH Keywords

degree-constrained subgraphsedge weights

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

Suppose that the edges of a graph are assigned labels from a \(k\)-set, or equivilently, the edges are partitioned into \(k\) parts. Each vertex \(v\) has an associated multiset \(X_v\) consisting of the labels on its incident edges. The partition is a (proper) vertex coloring if for every edge \(uv\), \(X_u \neq X_v\). The authors show that the edges of any graph (except those containing a component isomorphic to \(K_2\)) have a partition into four parts such that the associated multisets form a vertex coloring. Moreover, if the minimum degree is at least 1000, then the edges can be partitioned into three parts yielding a vertex coloring. This paper is well written and the result is interesting.

Recommendations

• Vertex partitions of \(r\)-edge-colored graphs
• Partitions and edge colourings of multigraphs
• scientific article; zbMATH DE number 2146626
• Vertex-distinguishing edge colorings of graphs
• On vertex-parity edge-colorings
• Graph colourings and partitions
• Vertex-distinguishing proper edge-colorings
• scientific article; zbMATH DE number 6729895
• On vertex-distinguishing edge colorings of graphs
• scientific article; zbMATH DE number 7528064

Cites work

• Edge weights and vertex colours
• scientific article; zbMATH DE number 140040 (Why is no real title available?)
• Matching theory
• The Harmonious Chromatic Number of Bounded Degree Graphs
• Vertex-colouring edge-weightings
• Vertex-distinguishing edge colorings of graphs
• Vertex-distinguishing proper edge-colorings

Cited in

(60)

• A new type of edge-derived vertex coloring
• Graphs are \((1, \varDelta + 1)\)-choosable
• New bounds for locally irregular chromatic index of bipartite and subcubic graphs
• Graphs with maximum average degree less than \(\frac{11}{4}\) are \((1, 3)\)-choosable
• Distant set distinguishing edge colourings of graphs
• Multi-set neighbor distinguishing 3-edge coloring
• Distant total sum distinguishing index of graphs
• A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs
• A note on edge weightings inducing proper vertex colorings
• Further evidence towards the multiplicative 1-2-3 conjecture
• Neighbour-distinguishing labellings of families of graphs
• Dense Eulerian graphs are (1, 3)-choosable
• The 1-2-3 conjecture almost holds for regular graphs
• On colour-blind distinguishing colour pallets in regular graphs
• On the complexity of determining the irregular chromatic index of a graph
• An oriented version of the 1-2-3 conjecture
• On decomposing regular graphs into locally irregular subgraphs
• Vertex-coloring 3-edge-weighting of some graphs
• Total weight choosability of graphs with bounded maximum average degree
• Colorful edge decomposition of graphs: some polynomial cases
• Complexity of the improper twin edge coloring of graphs
• A note on breaking small automorphisms in graphs
• Degree constrained subgraphs
• On twin edge colorings of graphs
• A relaxed case on 1-2-3 conjecture
• On the standard (2,2)-conjecture
• On decomposing graphs of large minimum degree into locally irregular subgraphs
• The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture
• Graphs with vertex-coloring and detectable 2-edge-weighting
• Weight choosability of graphs
• Algorithmic complexity of proper labeling problems
• Can colour-blind distinguish colour palettes?
• Colour-blind can distinguish colour pallets
• Computation of lucky number of planar graphs is NP-hard
• Multiplicative vertex-colouring weightings of graphs
• Total weight choosability of Cartesian product of graphs
• Edge-partitions of planar graphs and their game coloring numbers
• Total weight choosability for Halin graphs
• Permanent index of matrices associated with graphs
• Graphs with multiplicative vertex-coloring 2-edge-weightings
• Every graph is (2,3)-choosable
• The neighbour-sum-distinguishing edge-colouring game
• scientific article; zbMATH DE number 6729895 (Why is no real title available?)
• Total weight choosability of graphs
• The sigma chromatic number of a graph
• Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
• A proof of the multiplicative 1-2-3 conjecture
• The weak (2, 2)-labelling problem for graphs with forbidden induced structures
• A solution to the 1-2-3 conjecture
• The strong (2, 2)-conjecture for more classes of graphs
• The irregularity strength of dense graphs -- on asymptotically optimal solutions of problems of Faudree, Jacobson, Kinch and Lehel
• Degree-balanced decompositions of cubic graphs
• The 1-2-3 conjecture holds for graphs with large enough minimum degree
• On proper 2-labellings distinguishing by sums, multisets or products
• On a graph labelling conjecture involving coloured labels
• Decomposability of regular graphs to 4 locally irregular subgraphs
• Vertex partitions of \(r\)-edge-colored graphs
• Edge colouring by total labellings
• 1,2 conjecture-the multiplicative version
• Lucky labelings of graphs

This page was built for publication: Vertex colouring edge partitions

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