Degree-doubling graph families

DOI10.1137/120887242MaRDI QIDQ2870523zbMATH OpenOpenAlexFDO

Authors János Körner, Irene Muzi

Publication date 21 January 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphrainbow coloringplanar point setrainbow chromatic number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of tessellation and tiling problems (05B45) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: Let G be a family of n-vertex graphs of uniform degree 2 with the property that the union of any two member graphs has degree four. We determine the leading term in the asymptotics of the largest cardinality of such a family. Several analogous problems are discussed.

Recommendations

• scientific article; zbMATH DE number 4162938
• Degree sets of degree uniform graphs
• scientific article; zbMATH DE number 4103105
• A family of graphs and the degree/diameter problem
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree

Cited in

(5)

• Improved upper bounds on even-cycle creating Hamilton paths
• On \(k\)-neighbor separated permutations
• Triangle-different Hamiltonian paths
• New bounds on even cycle creating Hamiltonian paths using expander graphs
• Rainbow colorings of some geometrically defined uniform hypergraphs in the plane

This page was built for publication: Degree-doubling graph families

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