BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
This short note proves that every incomplete k-list-critical graph has average degree at least k−1+k2−2k+2k−3. This improves the best known bound for k=4,5,6. The same bound holds for online k-list-critical graphs.
We improve the best known bounds on average degree of k-list-critical graphs for k≥6. Specifically, for k≥7 we show that every non-complete k-list-critical graph has average degree at least k−1+k4−2k3−11k2+28k−14(k−3)2(2k−3) and every non-complete 6-list-critical graph has average degree at least 5+76693. The same bounds hold for online k-list-critical graphs.
The 4 Color Theorem (4CT) implies that every n-vertex planar graph has an independent set of size at least 4n; this is best possible, as shown by the disjoint union of many copies of K4. In 1968, Erdős asked whether this bound on independence number could be proved more easily than the full 4CT. In 1976 Albertson showed (independently of the 4CT) that every n-vertex planar graph has an independent set of size at least 92n. Until now, this remained the best bound independent of the 4CT. Our main result improves this bound to 133n.
Many graph coloring proofs proceed by showing that a minimal counterexample to the theorem being proved cannot contain certain configurations, and then showing that each graph under consideration contains at least one such configuration; these configurations are called \emph{reducible} for that theorem. (A \emph{configuration} is a subgraph H, along with specified degrees dG(v) in the original graph G for each vertex of H.) We give a general framework for showing that configurations are reducible for edge-coloring. A particular form of reducibility, called \emph{fixability}, can be considered without reference to a containing graph. This has two key benefits: (i) we can now formulate necessary conditions for fixability, and (ii) the problem of fixability is easy for a computer to solve. The necessary condition of \emph{superabundance} is sufficient for multistars and we conjecture that it is sufficient for trees as well, which would generalize the powerful technique of Tashkinov trees. Via computer, we can generate thousands of reducible configurations, but we have short proofs for only a small fraction of these. The computer can write \LaTeX\ code for its proofs, but they are only marginally enlightening and can run thousands of pages long. We give examples of how to use some of these reducible configurations to prove conjectures on edge-coloring for small maximum degree. Our aims in writing this paper are (i) to provide a common context for a variety of reducible configurations for edge-coloring and (ii) to spur development of methods for humans to understand what the computer already knows.
We take an application of the Kernel Lemma by Kostochka and Yancey to its logical conclusion. The consequence is a sort of magical way to draw conclusions about list coloring (and online list coloring) just from the existence of an independent set incident to many edges. We use this to prove an Ore-degree version of Brooks' Theorem for online list-coloring. The Ore-degree of an edge xy in a graph G is θ(xy)=dG(x)+dG(y). The Ore-degree of G is θ(G)=maxxy∈E(G)θ(xy). We show that every graph with θ≥18 and ω≤2θ is online ⌊2θ⌋-choosable. In addition, we prove an upper bound for online list-coloring triangle-free graphs: χOL≤Δ+1−⌊41lg(Δ)⌋. Finally, we characterize Gallai trees as the connected graphs G with no independent set incident to at least ∣G∣ edges.
We prove that every k-list-critical graph (k≥7) on n≥k+2 vertices has at least 21(k−1+(k−c)(k−1)+k−3k−3)n edges where c=(k−3)(21−(k−1)(k−2)1). This improves the bound established by Kostochka and Stiebitz. The same bound holds for online k-list-critical graphs, improving the bound established by Riasat and Schauz. Both bounds follow from a more general result stating that either a graph has many edges or it has an Alon-Tarsi orientable induced subgraph satisfying a certain degree condition.
We prove bounds on the chromatic number χ of a vertex-transitive graph in terms of its clique number ω and maximum degree Δ. We conjecture that every vertex-transitive graph satisfies χ≤max{ω,⌈65Δ+3⌉} and we prove results supporting this conjecture. Finally, for vertex-transitive graphs with Δ≥13 we prove the Borodin-Kostochka conjecture, i.e., χ≤max{ω,Δ−1}.
Arguably the simplest variation of this style of proof as we avoid reducing to the cubic case entirely.
Lovász gave a short proof of Brooks' theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case. Then we show how to extend the result to (online) list coloring via the Kernel Lemma.
We characterize the initial positions from which the first player has a winning strategy in a certain two-player game. This provides a generalization of Hall's theorem. Vizing's edge coloring theorem follows from a special case.
We prove that every claw-free graph G that doesn't contain a clique on Δ(G)≥9 vertices can be Δ(G)−1 colored.
It is shown that any graph with maximum degree Δ in which the average degree of the induced subgraph on the set of all neighbors of any vertex exceeds 6k2+16k2Δ+k+6 is either (Δ−k)-colorable or contains a clique on more than Δ−2k vertices. In the k=1 case we improve the bound on the average degree to 32Δ+4 and the bound on the clique number to Δ−1. As corollaries, we show that every graph satisfies χ≤max{ω,Δ−1,4α} and every graph satisfies $χ\leq \max\set{ω, Δ- 1, \ceil{\frac{15 + \sqrt{48n + 73}}{4}}}$.
We prove that if G is a vertex critical graph with χ(G)≥Δ(G)+1−p≥4 for some p∈N and $ω(\fancy{H}(G)) \leq \frac{χ(G) + 1}{p + 1} - 2$, then G=Kχ(G) or G=O5. Here $\fancy{H}(G)$ is the subgraph of G induced on the vertices of degree at least χ(G). This simplifies and improves the results in the paper of Kostochka, Rabern and Stiebitz \cite{krs_one}.
We prove a general lemma about partitioning the vertex set of a graph into subgraphs of bounded degree. This lemma extends a sequence of results of Lovász, Catlin, Kostochka and Rabern.
We prove that χ(G)≤maxω(G),Δ2(G),(5/6)(Δ(G)+1) for every graph G with Δ(G)≥3. Here Δ2 is the parameter introduced by Stacho that gives the largest degree that a vertex v can have subject to the condition that v is adjacent to a vertex whose degree is at least as large as its own. This upper bound generalizes both Brooks' Theorem and the Ore-degree version of Brooks' Theorem.
We prove that Kχ(G) is the only critical graph G with χ(G)≥Δ(G)≥6 and ω(H(G))≤⌊2Δ(G)⌋−2. Here H(G) is the subgraph of G induced on the vertices of degree at least χ(G). Setting ω(H(G))=1 proves a conjecture of Kierstead and Kostochka.
We prove that if G is a graph and r1,...,rk∈Z≥0 such that ∑i=1kri≥Δ(G)+2−k then V(G) can be partitioned into sets V1,...,Vk such that Δ(G[Vi])≤ri and G[Vi] contains no non-complete ri-regular components for each 1≤i≤k. In particular, the vertex set of any graph G can be partitioned into ⌈3Δ(G)+2⌉ sets, each of which induces a disjoint union of triangles and paths.
We prove that every graph G for which ω(G)≥3/4(Δ(G)+1), has an independent set I such that ω(G−I)<ω(G). It follows that a minimum counterexample G to Reed's conjecture satisfies ω(G)<3/4(Δ(G)+1) and hence also χ(G)>⌈7/6ω(G)⌉. We also prove that if for every induced subgraph H of G we have χ(H)≤max⌈7/6ω(H)⌉,⌈2ω(H)+Δ(H)+1⌉, then we also have χ(G)≤⌈2ω(G)+Δ(G)+1⌉. This gives a generic proof of the upper bound for line graphs of multigraphs proved by King et al.
We improve upper bounds on the chromatic number proven independently in \cite{reedNote} and \cite{ingo}. Our main lemma gives a sufficient condition for two paths in graph to be completely joined. Using this, we prove that if a graph has an optimal coloring with more than 2ω singleton color classes, then it satisfies χ≤2ω+Δ+1. It follows that a graph satisfying n−Δ<α+2ω−1 must also satisfy χ≤2ω+Δ+1, improving the bounds in \cite{reedNote} and \cite{ingo}. We then give a simple argument showing that if a graph satisfies χ>2n+3−α, then it also satisfies χ(G)≤⌈2ω(G)+Δ(G)+1⌉. From this it follows that a graph satisfying n−Δ<α+ω also satisfies χ(G)≤⌈2ω(G)+Δ(G)+1⌉ improving the bounds in \cite{reedNote} and \cite{ingo} even further at the cost of a ceiling. In the next sections, we generalize our main lemma to constrained colorings (e.g. r-bounded colorings). We present a generalization of Reed's conjecture to r-bounded colorings and prove the conjecture for graphs with maximal degree close to their order. Finally, we outline some applications (in \cite{BorodinKostochka} and \cite{ColoringWithDoublyCriticalEdge}) of the theory presented here to the Borodin-Kostochka conjecture and coloring graphs containing a doubly critical edge.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.