Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userKH{o}nigs Line Coloring and Vizings Theorems for Graphings
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The classical theorem of Vizing states that every graph of maximum degree $d$ admits an edge-coloring with at most $d+1$ colors. Furthermore, as it was earlier shown by KH{o}nig, $d$ colors suffice if the graph is bipartite. We investigate the existence of measurable edge-colorings for graphings. A graphing is an analytic generalization of a bounded-degree graph that appears in various areas, such as sparse graph limits, orbit equivalence theory and measurable group theory. We show that every graphing of maximum degree $d$ admits a measurable edge-coloring with $d + O(sqrt{d})$ colors; furthermore, if the graphing has no odd cycles, then $d+1$ colors suffice. In fact, if a certain conjecture about finite graphs that strengthens Vizings theorem is true, then our method will show that $d+1$ colors are always enough.
rate research
Read More
It is well-known that any finite $Pi^{0}_{1}$-class of $2^{mathbb N}$ has a computable member. Then, how can we understand this in the context of reverse mathematics? In this note, we consider several very weak fragments of KH{o}nigs lemma to answer this qeustion.
The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? We answer this question in the affirmative for triangle-free graphs.
It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O(loglog n)$. This improves the previous bound of $O(log n)$ (McGuinness, 1996) and matches the known lower bound construction (Pawlik et al., 2013).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
