On asymptotic packing of convex geometric and ordered graphs

DOI10.1002/JGT.23002MaRDI QIDQ6062874zbMATH OpenFDO

Authors Jiaxi Nie, Ji Zeng

Publication date 6 November 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

convex geometric graphcyclic chromatic numberinterval chromatic numberordered graphpacking problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A convex geometric graph $G$ is said to be packable if there exist edge-disjoint copies of $G$ in the complete convex geometric graph $K_n$ covering all but $o(n^2)$ edges. We prove that every convex geometric graph with cyclic chromatic number at most $4$ is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most $3$ is packable. Arguments based on the average length of edges imply these results are best possible. We also identify a class of convex geometric graphs that are packable due to having many "long" edges.

Recommendations

• On asymptotic packing of geometric graphs
• Packing two graphs of order n having total size at most 2n-2
• Two theorems on packings of graphs
• On geometric graphs with no two edges in convex position
• Near packings of graphs

Cites work

• Asymptotic behavior of the chromatic index for hypergraphs
• Chromatic number of ordered graphs with forbidden ordered subgraphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Forbidden paths and cycles in ordered graphs and matrices
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• scientific article; zbMATH DE number 903456 (Why is no real title available?)
• scientific article; zbMATH DE number 2209719 (Why is no real title available?)
• On a packing and covering problem
• On asymptotic packing of geometric graphs
• On the Turán number of some ordered even cycles
• Ordered and convex geometric trees with linear extremal function
• Packing plane spanning trees and paths in complete geometric graphs
• Packing plane spanning trees into a point set
• Partitions of complete geometric graphs into plane trees
• The book thickness of a graph
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• The probabilistic method

This page was built for publication: On asymptotic packing of convex geometric and ordered graphs

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