Search

An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes. [ABSTRACT FROM AUTHOR]

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let q B( G ) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider q B( G ) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ = Δ( G ) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that q B( G ) ≤ 2 Δ + 8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, q B( G ) ≤ 2 Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and q B( G ) ≤ Δ + 1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ ≥ 4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, q B( G ) ≤ 2 Δ( G ) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and q B( G ) ≤ Δ( G ) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

For a natural unit interval order P, we describe proper colorings of the incomparability graph of P in the language of heaps. We also introduce a combinatorial operation, called a local flip , on the heaps. This operation defines an equivalence relation on the proper colorings, and the equivalence relation refines the ascent statistic introduced by Shareshian and Wachs. In addition, we define an analogue of noncommutative symmetric functions introduced by Fomin and Greene, with respect to P. We establish a duality between the chromatic quasisymmetric function of P and these noncommutative symmetric functions. This duality leads us to positive expansions of the chromatic quasisymmetric functions into several symmetric function bases. In particular, we present some partial results for the e-positivity conjecture. [ABSTRACT FROM AUTHOR]

An odd c - coloring of a graph is a proper c -coloring such that each non-isolated vertex has a color appearing an odd number of times within its open neighborhood. A proper conflict-free c - coloring of a graph is a proper c -coloring such that each non-isolated vertex has a color appearing exactly once within its neighborhood. Clearly, every proper conflict-free c -coloring is also an odd c -coloring. Cranston conjectured that every graph G with maximum average degree mad (G) < 4 c c + 2 (where c ≥ 4) has an odd c -coloring, and he proved this conjecture for c ∈ { 5 , 6 }. Note that the bound 4 c c + 2 is best possible. Cho et al. solved Cranston's conjecture for c ≥ 5 , strengthening the result by transitioning from odd c -coloring to proper conflict-free c -coloring. However, they did not provide all the extremal non-colorable graphs G with mad (G) = 4 c c + 2 , which remains an open question of interest. In this paper, we tackle this intriguing extremal problem. We aim to characterize all non-proper conflict-free c -colorable graphs G with mad (G) = 4 c c + 2 . For the case of c = 4 , Cranston's conjecture is not true, as evidenced by the existence of a counterexample: a graph whose every block is a 5-cycle. Cho et al. proved that a graph G with mad (G) < 22 9 and no induced 5-cycles has an odd 4-coloring. We improve this result by proving that a graph G with mad (G) ≤ 22 9 (with equality allowed) is not odd 4-colorable if and only if G belongs to a specific class of graphs. On the other hand, Cho et al. established that a planar graph with girth at least 5 has an odd 6-coloring; we improve it by proving that a planar graph without 4 − -cycles adjacent to 7 − -cycles also has an odd 6-coloring. [ABSTRACT FROM AUTHOR]

A graph in which the two end-vertices of every edge have distinct degrees is called locally irregular. An edge coloring of a graph G such that every color induces a locally irregular subgraph of G is said to be locally irregular. A graph G which admits a locally irregular edge coloring is called colorable. The Local Irregularity Conjecture claims that 3 colors are enough for locally irregular edge coloring of any colorable graph. Not so long ago the only known graphs which do not admit a locally irregular 3-edge coloring were the non-colorable graphs, all of which are cacti. This fact motivated us to study locally irregular 3-edge colorings of cacti, which first resulted with the finding of the bow-tie graph B , a colorable cactus graph which requires 4 colors for a locally irregular edge coloring. As the graph B disproves the stated form of the Local Irregularity Conjecture, here we continue the study of locally irregular 3-edge colorings of cacti in relation to the conjecture. In this paper we confirm that all other cacti are locally irregular 3-edge colorable. This result makes us to believe that B is the only counterexample to the conjecture not only in the class of cacti, but also in general. [ABSTRACT FROM AUTHOR]

Brooks' theorem states that for a graph G , if Δ (G) ≥ 3 and ω (G) ≤ Δ (G) , then χ (G) ≤ Δ (G). In this paper, we show that this chromatic bound can be further strengthened on (P 6 , C 4 , H) -free graphs, where H ∈ { b u l l , d i a m o n d }. In particular, we prove that for a (P 6 , C 4 , b u l l) -free graph G , if Δ (G) ≥ 9 and ω (G) ≤ Δ (G) − 1 , then χ (G) ≤ Δ (G) − 1. We also prove that for a (P 6 , C 4 , d i a m o n d) -free graph G , if Δ (G) ≥ 5 and ω (G) ≤ Δ (G) − 1 , then χ (G) ≤ Δ (G) − 1. We also show that similar results hold for (P 10 , p a w) -free graphs and (P 5 , C 5) -free graphs. These results validate the Borodin–Kostochka conjecture on these graph classes. [ABSTRACT FROM AUTHOR]

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 3. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of (pseudo-)circle arrangements. In this paper the conjecture is verified for △ - saturated pseudocircle arrangements, i.e., for arrangements where one color class of the 2-coloring of faces consists of triangles only, as well as for further classes of (pseudo-)circle arrangements. These results are complemented by a construction which maps △ -saturated arrangements with a pentagonal face to arrangements with 4-chromatic 4-regular arrangement graphs. This corona construction has similarities with the crowning construction introduced by Koester (1985). Based on exhaustive experiments with small arrangements we propose three strengthenings of the original conjecture. We further investigate fractional colorings. It is shown that the arrangement graph of every arrangement A of pairwise intersecting pseudocircles is "close" to being 3-colorable. More precisely, the fractional chromatic number χ f (A) of the arrangement graph is bounded from above by χ f (A) ≤ 3 + O (1 n) , where n is the number of pseudocircles of A. Furthermore, we construct an infinite family of 4-edge-critical 4-regular planar graphs which are fractionally 3-colorable. This disproves a conjecture of Gimbel, Kündgen, Li, and Thomassen (2019). [ABSTRACT FROM AUTHOR]

It is known that the so-called Beck’s conjecture, i.e. the equality of the finite clique and chromatic numbers of a zero-divisor graph, holds for partially ordered sets Halaš and Jukl (Discrete Math 309(13):4584–4589, 2009). In this paper we present a simple direct proof of this fact. Also, the case when the finiteness assumption of the clique number is omitted is investigated. We have shown that the conjecture fails in general and a bunch of counterexamples is presented. [ABSTRACT FROM AUTHOR]

Motivated by the study of greedy algorithms for graph coloring, Bernshteyn and Lee introduced a generalization of graph degeneracy, which is called weak degeneracy. In this paper, we show the lower bound of the weak degeneracy for d -regular graphs is exactly ⌊ d / 2 ⌋ + 1 , which is tight. This result refutes the conjecture of Bernshteyn and Lee on this lower bound. [ABSTRACT FROM AUTHOR]

The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree Δ ≥ 3 that is not the complete graph K Δ + 1 or the complete bipartite graph K Δ , Δ admits an equitable coloring with Δ colors. For planar graphs, the conjecture has been confirmed for Δ ≥ 13 by Yap and Zhang and for 9 ≤ Δ ≤ 12 by Nakprasit. In this paper, we present a proof that confirms the conjecture for graphs embeddable into a surface with non-negative Euler characteristic with maximum degree Δ ≥ 9 and for planar graphs with maximum degree Δ ≥ 8. [ABSTRACT FROM AUTHOR]

For a vertex a in H , we denote by ∂ H (a) the set of edges incident with a. An H -coloring of a graph G is a proper edge-coloring f : E (G) → E (H) such that for each vertex u in G , there exists a vertex a in H such that f (∂ G (u)) = ∂ H (a). In this paper, we introduce some graphs H such that H -colorability of 4-regular graphs is meaningful and related to some of their properties, such as an even cycle decomposition of size 3 and an even 2-factor. In addition, we formulate a conjecture on H -coloring of the line graph of some cubic graphs. Partial solutions to the conjecture are also presented. [ABSTRACT FROM AUTHOR]

The Borodin-Kostochka conjecture says that for a connected graph G , if Δ (G) ≥ 9 , then χ (G) ≤ max ⁡ { Δ (G) − 1 , ω (G) }. In this paper, we prove that the conjecture holds for hammer-free graphs, where a hammer is the graph obtained by identifying one vertex of a triangle and one end vertex of an induced path with three vertices. [ABSTRACT FROM AUTHOR]