Clusters in a multigraph with elevated density

MaRDI QIDQ870066zbMATH OpenFDO

Authors Mark K. Goldberg

Publication date 12 March 2007

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/127209, http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r10.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Review text

Summary: In this paper, we prove that in a multigraph whose density \(\Gamma\) exceeds the maximum vertex degree \(\Delta\), the collection of minimal clusters (maximally dense sets of vertices) is cycle-free. We also prove that for multigraphs with \(\Gamma > \Delta + 1\), the size of any cluster is bounded from the above by \((\Gamma - 3)/ (\Gamma - \Delta -1)\). Finally, we show that two well-known lower bounds for the chromatic index of a multigraph are equal.

Recommendations

• Edge coloring multigraphs without small dense subsets
• scientific article; zbMATH DE number 3918395
• A note concerning the chromatic index of multigraphs
• Asymptotics of the chromatic index for multigraphs
• The maximum chromatic index of multigraphs with given \(\Delta \) and \(\mu \)

Cited in

(2)

• Cluster adjacency beyond MHV
• scientific article; zbMATH DE number 7058666 (Why is no real title available?)

This page was built for publication: Clusters in a multigraph with elevated density

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